Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Plane Graphs with Parity Constraints
verfasst von : Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Günter Rote, Bettina Speckmann, Birgit Vogtenhuber
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
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
Let
S
be a set of
n
points in general position in the plane. Together with
S
we are given a set of parity constraints, that is, every point of
S
is labeled either even or odd. A graph
G
on
S
satisfies the parity constraint of a point
p
∈
S
, if the parity of the degree of
p
in
G
matches its label. In this paper we study how well various classes of planar graphs can satisfy arbitrary parity constraints. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudo-triangulation which satisfy all but at most three parity constraints. With triangulations we can satisfy about 2/3 of all parity constraints. In contrast, for a given simple polygon
H
with polygonal holes on
S
, we show that it is NP-complete to decide whether there exists a triangulation of
H
that satisfies all parity constraints.