On Graphs Supported by Line SetsDujmović, Vida and Evans, William S. and Kobourov, Stephen G. and Liotta, Giuseppe and Weibel, Christophe and Wismath, Stephen (2011) On Graphs Supported by Line Sets. In: Graph Drawing 18th International Symposium, GD 2010, September 2124, 2010 , pp. 177182(Official URL: http://dx.doi.org/10.1007/9783642184697_16). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642184697_16
AbstractFor a set S of n lines labeled from 1 to n, we say that S supports an nvertex planar graph G if for every labeling from 1 to n of its vertices, G has a straightline crossingfree 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 nvertex 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 nvertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all nvertex planar graphs.
Actions (login required)
