Advertisement
Published in:
2013 | OriginalPaper | Chapter
Strongly-Connected Outerplanar Graphs with Proper Touching Triangle Representations
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A
proper touching triangle representation
$\mathcal{R}$
of an
n
-vertex planar graph consists of a triangle divided into
n
non-overlapping triangles. A pair of triangles are considered to be adjacent if they share a partial side of positive length. Each triangle in
$\mathcal{R}$
represents a vertex, while each pair of adjacent triangles represents an edge in the planar graph. We consider the problem of determining when a proper touching triangle representation exists for a
strongly-connected outerplanar graph
, which is biconnected and after the removal of all degree-2 vertices and outeredges, the resulting
connected
subgraph only has chord edges (w.r.t. the original graph). We show that such a graph has a proper representation if and only if the graph has at most two
internal faces
(
i.e.,
faces with no outeredges).