Record link: 
http://hdl.handle.net/20.500.12708/58708
-
Title: 
Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs
-
Citation: 
Bhore, S., Löffler, M., Nickel, S., & Nöllenburg, M. (2021). Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs. In Graph Drawing and Network Visualization. GD 2021 (pp. 304–317). Springer. https://doi.org/10.1007/978-3-030-92931-2_22
-
Publisher DOI: 
10.1007/978-3-030-92931-2_22
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Bhore, Sujoy 
Löffler, Maarten 
Nickel, Soeren 
Nöllenburg, Martin 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Graph Drawing and Network Visualization. GD 2021 
-
Volume: 
12868
-
Date (published): 
2021
-
Event name: 
29th International Symposium on Graph Drawing and Network Visualization (GD 2021) 
-
Event date: 
14-Sep-2021 - 17-Sep-2021
-
Event place: 
Tübingen, Germany
-
Number of Pages: 
14
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Abstract: 
A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
Mathematik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

219
checked on Nov 23, 2023

Google ScholarTM

Check