E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Graph Drawing and Network Visualization. GD 2019
-
Volume:
11904
-
Date (published):
2019
-
Event name:
International Symposium on Graph Drawing and Network Visualization (GD 2019)
-
Event date:
17-Sep-2019 - 20-Sep-2019
-
Event place:
Prag, Czechia
-
Number of Pages:
15
-
Publisher:
Springer, Cham
-
Peer reviewed:
Yes
-
Abstract:
A strict confluent (SC) graph drawing is a drawing of a graph
with vertices as points in the plane, where vertex adjacencies are represented
not by individual curves but rather by unique smooth paths
through a planar system of junctions and arcs. If all vertices of the graph
lie in the outer face of the drawing, the drawing is called a strict outerconfluent
(SOC) drawing. SC and SOC graphs were first considered by
Eppstein et al. in Graph Drawing 2013. Here, we establish several new
relationships between the class of SC graphs and other graph classes,
in particular string graphs and unit-interval graphs. Further, we extend
earlier results about special bipartite graph classes to the notion of strict
outerconfluency, show that SOC graphs have cop number two, and establish
that tree-like (Δ-)SOC graphs have bounded cliquewidth.
