On graphs supported by line sets

Vida Dujmović, William Evans, Stephen Kobourov, Giuseppe Liotta, Christophe Weibel, Stephen Wismath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationGraph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
Pages177-182
Number of pages6
DOIs
StatePublished - 2011
Event18th International Symposium on Graph Drawing, GD 2010 - Konstanz, Germany
Duration: Sep 21 2010Sep 24 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6502 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Symposium on Graph Drawing, GD 2010
Country/TerritoryGermany
CityKonstanz
Period9/21/109/24/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On graphs supported by line sets'. Together they form a unique fingerprint.

Cite this