Proportional Contact Representations of 4Connected Planar GraphsAlam, Muhammed Jawaherul and Kobourov, Stephen G. (2013) Proportional Contact Representations of 4Connected Planar Graphs. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 211223(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractIn a contact representation of a planar graph, vertices are represented by interiordisjoint polygons and two polygons share a nonempty common boundary when the corresponding vertices are adjacent. In the weighted version, a weight is assigned to each vertex and a contact representation is called proportional if each polygon realizes an area proportional to the vertex weight. In this paper we study proportional contact representations of 4connected internally triangulated planar graphs. The best known lower and upper bounds on the polygonal complexity for such graphs are 4 and 8, respectively. We narrow the gap between them by proving the existence of a representation with complexity 6. We then disprove a 10year old conjecture on the existence of a Hamiltonian canonical cycle in a 4connected maximal planar graph, which also implies that a previously suggested method for constructing proportional contact representations of complexity 6 for these graphs will not work. Finally we prove that it is NPhard to decide whether a 4connected planar graph admits a proportional contact representation using only rectangles.
Actions (login required)
