𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Number of Acute Triangles in a Straight-Line Embedding of a Maximal Planar Graph

✍ Scribed by Atsushi Kaneko; Hiroshi Maehara; Mamoru Watanabe

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
80 KB
Volume
75
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we show that any maximal planar graph with m triangles except the unbounded face can be transformed into a straight-line embedding in which at least WmΓ‚3X triangles are acute triangles. Moreover, we show that any maximal outerplanar graph can be transformed into a straight-line embedding in which all faces are acute triangles except the unbounded face.

πŸ“œ SIMILAR VOLUMES

On the number of hamiltonian cycles in a
On the number of hamiltonian cycles in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 243 KB πŸ‘ 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ β‰₯ 12. We also pro

On the number of cycles of length 4 in a
On the number of cycles of length 4 in a maximal planar graph
✍ Ahmad Fawzi Alameddine πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 148 KB πŸ‘ 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ β‰₯

On the number of maximal bipartite subgr
On the number of maximal bipartite subgraphs of a graph
✍ Jesper Makholm Byskov; Bolette AmmitzbΓΈll Madsen; Bjarke Skjernaa πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 72 KB πŸ‘ 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ΒΌ O(1:8613 n ) and give an algorithm that finds all maximal

On the maximum number of cycles in a pla
On the maximum number of cycles in a planar graph
✍ R. E. L. Aldred; Carsten Thomassen πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__β€‰βˆ’β€‰__p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__β€‰βˆ’β€‰1^ = __o__(2^__r__β€‰βˆ’β€‰1^) cycles. The planar result is best possib