TY - GEN
T1 - Equilateral L-contact graphs
AU - Chaplick, Steven
AU - Kobourov, Stephen G.
AU - Ueckerdt, Torsten
PY - 2013
Y1 - 2013
N2 - We consider L-graphs, that is contact graphs of axis-aligned L-shapes in the plane, all with the same rotation. We provide several characterizations of L-graphs, drawing connections to Schnyder realizers and canonical orders of maximally planar graphs. We show that every contact system of L's can always be converted to an equivalent one with equilateral L's. This can be used to show a stronger version of a result of Thomassen, namely, that every planar graph can be represented as a contact system of square-based cuboids. We also study a slightly more restricted version of equilateral L-contact systems and show that these are equivalent to homothetic triangle contact representations of maximally planar graphs. We believe that this new interpretation of the problem might allow for efficient algorithms to find homothetic triangle contact representations, that do not use Schramm's monster packing theorem.
AB - We consider L-graphs, that is contact graphs of axis-aligned L-shapes in the plane, all with the same rotation. We provide several characterizations of L-graphs, drawing connections to Schnyder realizers and canonical orders of maximally planar graphs. We show that every contact system of L's can always be converted to an equivalent one with equilateral L's. This can be used to show a stronger version of a result of Thomassen, namely, that every planar graph can be represented as a contact system of square-based cuboids. We also study a slightly more restricted version of equilateral L-contact systems and show that these are equivalent to homothetic triangle contact representations of maximally planar graphs. We believe that this new interpretation of the problem might allow for efficient algorithms to find homothetic triangle contact representations, that do not use Schramm's monster packing theorem.
UR - http://www.scopus.com/inward/record.url?scp=84893038091&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893038091&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45043-3_13
DO - 10.1007/978-3-642-45043-3_13
M3 - Conference contribution
AN - SCOPUS:84893038091
SN - 9783642450426
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 139
EP - 151
BT - Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Revised Papers
PB - Springer-Verlag
T2 - 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013
Y2 - 19 June 2013 through 21 June 2013
ER -