Contact Representations of Directed Planar Graphs in 2D and 3D
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
11949 LNCS
Pages
82-93
Date Issued
2019
Author(s)
Chan C.-H
Abstract
In applications such as VLSI floorplanning and cartogram design, vertices of a graph are represented by geometric objects and edges are captured by contacts between those objects, which are examples of a drawing style called contact graph representations. We study the feasibility of using line segments, triangles and tetrahedra to realize point-side contact representations for a number of graph classes including oriented versions of outerplanar graphs, 2-trees and 3-trees. Our main results show that every orientation of a maximal outerplanar graph of out-degree at most two, a 2-tree of out-degree at most two, and a planar 3-tree of out-degree at most four enjoy point-side contact representations using line segments, triangles, and tetrahedra, respectively. Unlike undirected graphs for which a fairly large amount of results can be found in the literature in the study of contact representations, directed graphs remain largely unexplored, and our study advances this line of research a step further. ? 2019, Springer Nature Switzerland AG.
Subjects
Combinatorial optimization; Geometry; Graphic methods; Contact graphs; Drawing styles; Geometric objects; Large amounts; Outerplanar graph; Planar graph; Undirected graph; VLSI floorplanning; Directed graphs
SDGs
Type
conference paper