Weak unit disk and interval representation of graphs

DOI10.1007/978-3-662-53174-7_17MaRDI QIDQ2827814zbMATH OpenOpenAlexFDO

Authors Md. Jawaherul Alam, Stephen G. Kobourov, Sergey Pupyrev, Jackson Toeniskoetter

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.6928, http://hdl.handle.net/10995/102767

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study a variant of intersection representations with unit balls, that is, 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 sets, the goal is to represent the vertices of the graph by unit balls so that the balls representing 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 edge-partition. On the other hand, every series-parallel graph admits such a representation with unit disks for any near/far labeling of the edges. We also show that the representation problem on the line is equivalent to a variant of a graph coloring. We give examples of girth-4 planar and girth-3 outerplanar graphs that have no such representation with unit intervals. On the other hand, all triangle-free outerplanar graphs and all graphs with maximum average degree less than 26/11 can always be represented. In particular, this gives a simple proof of representability of all planar graphs with large girth.

Recommendations

• Unit disk graphs
• Obedient plane drawings for disk intersection graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Threshold-coloring and unit-cube contact representation of planar graphs
• Threshold-coloring and unit-cube contact representation of graphs

Cites work

• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• A linear-time algorithm for proper interval graph recognition
• Approximate proximity drawings
• Coloring with no 2-colored \(P_4\)'s
• Colouring the real line
• Decomposing a planar graph into degenerate graphs
• Difference graphs
• Distance Graphs on the Integers
• Graph Sandwich Problems
• Integer realizations of disk and segment graphs
• On representing graphs by touching cuboids
• On the maximum average degree and the oriented chromatic number of a graph
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Star coloring high girth planar graphs
• Star coloring of sparse graphs
• Threshold graphs and related topics
• Threshold-coloring and unit-cube contact representation of graphs
• Topology of series-parallel networks
• Unit contact representations of grid subgraphs with regular polytopes in 2D and 3D
• Unit disk graph recognition is NP-hard

Cited in

(2)

• Threshold-coloring and unit-cube contact representation of planar graphs
• Threshold-coloring and unit-cube contact representation of graphs

This page was built for publication: Weak unit disk and interval representation of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827814)