next up previous
Next: Problem 70: Yao-Yao Graph Up: The Open Problems Project Previous: Problem 68: Rolling a


Problem 69: Isoceles Planar Graph Drawing

Statement
Given a planar graph that is interior triangulated (all interior faces are triangles), is there a staight-line drawing of the graph such that each face is an isoceles triangle (i.e., it has two equal-length sides)?

The problem is worth studying both when the drawing must be planar (no crossings allowed) and when it is not.

If such drawings exist, then it is also worth studying what grid-size is needed, and whether it can be done with integer coordinates at all. If such drawings do not always exist, NP-hardness should be investigated.

Origin
Joe Malkevitch at Graph Drawing '99.
Status/Conjectures
Settled negatively in 2010: [Fra10].
Partial and Related Results
If the graph is a planar 3-tree (i.e., can be obtained by starting from a triangle and repeatedly adding a vertex of degree 3 inside a face, adjacent to all other vertices in the face), then such a drawing can easily be obtained by always placing the vertex at the centroid of the face. However, this drawing will in general be non-planar.

Of particular interest therefore, are planar graphs of treewidth 4 and higher.

The problem was solved negatively in [Fra10]: Theorem: "There exists an infinite class of maximal planar graphs that admit no isosceles planar drawing." Frati raises the new question of whether or not every triangulation admits a possibly nonplanar isosceles drawing.

Categories
graph drawing; planar graphs
Entry Revision History
T. Biedl, 2 Dec. 2008; J. O'Rourke, 29 Dec. 2008; J. Malkevitch, 10 Jul 2011.

Bibliography

Fra10
F. Frati.
A note on isosceles planar graph drawing.
Information Processing Letters, 110(12-13):507-509, 2010.


next up previous
Next: Problem 70: Yao-Yao Graph Up: The Open Problems Project Previous: Problem 68: Rolling a
The Open Problems Project - December 04, 2015