Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102767
Title: Weak unit disk and interval representation of graphs
Authors: Alam, M. J.
Kobourov, S. G.
Pupyrev, S.
Toeniskoetter, J.
Issue Date: 2016
Publisher: Springer Verlag
Citation: Weak unit disk and interval representation of graphs / M. J. Alam, S. G. Kobourov, S. Pupyrev, et al. — DOI 10.1007/978-3-662-53174-7_17 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2016. — Vol. 9224 LNCS. — P. 237-251.
Abstract: We study a variant of intersection representations with unit balls: unit disks in the plane and unit intervals on the line. Given a planar graph and a bipartition of the edges of the graph into near and far edges, the goal is to represent the vertices of the graph by unit-size balls so that the balls for two adjacent vertices intersect if and only if the corresponding edge is near. We consider the problem in the plane and prove that it is NP-hard to decide whether such a representation exists for a given edgepartition. On the other hand, we show that series-parallel graphs (which include outerplanar graphs) admit such a representation with unit disks for any near/far bipartition of the edges. The unit-interval on the line variant is equivalent to threshold graph coloring, in which context it is known that there exist girth-3 planar graphs (even outerplanar graphs) that do not admit such coloring. We extend this result to girth-4 planar graphs. On the other hand, we show that all triangle-free outerplanar graphs and all planar graphs with maximum average degree less than 26/11 have such a coloring, via unit-interval intersection representation on the line. This gives a simple proof that all planar graphs with girth at least 13 have a unit-interval intersection representation on the line. © Springer International Publishing Switzerland 2016.
Keywords: GRAPHIC METHODS
ADJACENT VERTICES
INTERSECTION REPRESENTATIONS
MAXIMUM AVERAGE DEGREE
OUTERPLANAR GRAPH
REPRESENTATION OF GRAPHS
SERIES-PARALLEL GRAPH
THRESHOLD GRAPHS
UNIT INTERVALS
GRAPH THEORY
URI: http://hdl.handle.net/10995/102767
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84981523774
PURE ID: 1094541
fa75325e-54cc-4b80-9503-b5d44967eaa3
ISSN: 3029743
ISBN: 9783662531730
DOI: 10.1007/978-3-662-53174-7_17
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84981523774.pdf323,85 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.