TY - GEN
T1 - Recognizing a DOG is Hard but not when it is Thin and Unit
AU - Evans, Will
AU - Garderen, Mereke van
AU - Löffler, Maarten
AU - Polishchuk, Valentin
PY - 2016
Y1 - 2016
N2 - We define the notion of disk-obedience for a set of disks in the plane and give results for disk-obedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.
AB - We define the notion of disk-obedience for a set of disks in the plane and give results for disk-obedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.
KW - graph drawing
KW - planar graphs
KW - disk intersection graphs
U2 - 10.4230/LIPIcs.FUN.2016.16
DO - 10.4230/LIPIcs.FUN.2016.16
M3 - Conference contribution
T3 - LIPIcs
SP - 16:1-16:12
BT - Proc. 8th International Conference on Fun with Algorithms
ER -