Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Bar 1-Visibility Drawings of 1-Planar Graphs
verfasst von : Shaheena Sultana, Md. Saidur Rahman, Arpita Roy, Suraiya Tairin
Erschienen in: Applied Algorithms
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A bar 1-visibility drawing of a graph
G
is a drawing of
G
where each vertex is drawn as a horizontal line segment called a bar, each edge is drawn as a vertical line segment between its incident vertices such that each edge crosses at most one bar. A graph
G
is bar 1-visible if
G
has a bar 1-visibility drawing. A graph
G
is 1-planar if
G
can be drawn in the plane such that each edge has at most one crossing. In this paper we give
O
(
n
) time algorithms to find bar 1-visibility drawings of diagonal grid graphs, maximal outer 1-planar graphs, recursive quadrangle 1-planar graphs and pseudo double wheel 1-planar graphs, where
n
is the number of vertices in the input graph.