TY - GEN
T1 - On graphs supported by line sets
AU - Dujmović, Vida
AU - Evans, William
AU - Kobourov, Stephen
AU - Liotta, Giuseppe
AU - Weibel, Christophe
AU - Wismath, Stephen
N1 - Funding Information:
Research supported in part by: NSERC, MIUR under project AlgoDEEP prot. 2008TFBWL4. The research in this paper started during the McGill/INRIA Workshop at Bellairs. The authors thank the organizers and the other participants for useful discussions.
PY - 2011
Y1 - 2011
N2 - For a set S of n lines labeled from 1 to n, we say that S supports an n-vertex planar graph G if for every labeling from 1 to n of its vertices, G has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of n parallel lines supports all n-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more "powerful" than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of n lines that intersect in a common point supports all n-vertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all n-vertex planar graphs.
AB - For a set S of n lines labeled from 1 to n, we say that S supports an n-vertex planar graph G if for every labeling from 1 to n of its vertices, G has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of n parallel lines supports all n-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more "powerful" than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of n lines that intersect in a common point supports all n-vertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all n-vertex planar graphs.
UR - http://www.scopus.com/inward/record.url?scp=79952268624&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952268624&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-18469-7_16
DO - 10.1007/978-3-642-18469-7_16
M3 - Conference contribution
AN - SCOPUS:79952268624
SN - 9783642184680
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 177
EP - 182
BT - Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
T2 - 18th International Symposium on Graph Drawing, GD 2010
Y2 - 21 September 2010 through 24 September 2010
ER -