Next: Problem 70: Yao-Yao Graph a Spanner?
Previous: Problem 68: Rolling a Die over a Labeled Board
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.
Joe Malkevitch at Graph Drawing ’99.
Settled negatively in 2010: [Fra10].
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.
graph drawing; planar graphs
T. Biedl, 2 Dec. 2008; J. O’Rourke, 29 Dec. 2008; J. Malkevitch, 10 Jul 2011.
F. Frati. A note on isosceles planar graph drawing. Information Processing Letters, 110(12-13):507–509, 2010.