TY - GEN
T1 - Contact graphs of circular arcs
AU - Alam, Md Jawaherul
AU - Eppstein, David
AU - Kaufmann, Michael
AU - Kobourov, Stephen G.
AU - Pupyrev, Sergey
AU - Schulz, André
AU - Ueckerdt, Torsten
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is realized by an endpoint of one arc touching the interior of another. A graph is (2, k)-sparse if every s-vertex subgraph has at most 2s − k edges, and (2, k)-tight if in addition it has exactly 2n−k edges, where n is the number of vertices. Every graph with a CCA-representation is planar and (2, 0)-sparse, and it follows from known results that for k ≥ 3 every (2, k)-sparse graph has a CCA-representation. Hence the question of CCA-representability is open for (2, k)-sparse graphs with 0 ≤ k ≤ 2. We partially answer this question by computing CCArepresentations for several subclasses of planar (2, 0)-sparse graphs. Next, we study CCA-representations in which each arc has an empty convex hull. We show that every plane graph of maximum degree 4 has such a representation, but that finding such a representation for a plane (2, 0)-tight graph with maximum degree 5 is NP-complete. Finally, we describe a simple algorithm for representing plane (2, 0)-sparse graphs with wedges, where each vertex is represented with a sequence of two circular arcs (straight-line segments).
AB - We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is realized by an endpoint of one arc touching the interior of another. A graph is (2, k)-sparse if every s-vertex subgraph has at most 2s − k edges, and (2, k)-tight if in addition it has exactly 2n−k edges, where n is the number of vertices. Every graph with a CCA-representation is planar and (2, 0)-sparse, and it follows from known results that for k ≥ 3 every (2, k)-sparse graph has a CCA-representation. Hence the question of CCA-representability is open for (2, k)-sparse graphs with 0 ≤ k ≤ 2. We partially answer this question by computing CCArepresentations for several subclasses of planar (2, 0)-sparse graphs. Next, we study CCA-representations in which each arc has an empty convex hull. We show that every plane graph of maximum degree 4 has such a representation, but that finding such a representation for a plane (2, 0)-tight graph with maximum degree 5 is NP-complete. Finally, we describe a simple algorithm for representing plane (2, 0)-sparse graphs with wedges, where each vertex is represented with a sequence of two circular arcs (straight-line segments).
UR - http://www.scopus.com/inward/record.url?scp=84951855468&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84951855468&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21840-3_1
DO - 10.1007/978-3-319-21840-3_1
M3 - Conference contribution
AN - SCOPUS:84951855468
SN - 9783319218397
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 13
BT - Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Stege, Ulrike
PB - Springer-Verlag
T2 - 14th International Symposium on Algorithms and Data Structures, WADS 2015
Y2 - 5 August 2015 through 7 August 2015
ER -