Embeddings of planar graphs that minimize the number of long face cycles

Gerhard Woeginger

doi:10.1016/S0167-6377(02)00119-0

Embeddings of planar graphs that minimize the number of long face cycles

Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

5 Downloads (Pure)

Abstract

We consider the problem of finding embeddings of planar graphs that minimize the number of long-face cycles. We prove that for any k≥4, it is NP-complete to find an embedding that minimizes the number of face cycles of length at least k.

Original language	English
Pages (from-to)	167-168
Journal	Operations research letters
Volume	30
Issue number	3
DOIs	https://doi.org/10.1016/S0167-6377(02)00119-0
Publication status	Published - 2002

Keywords

METIS-208617
Computational Complexity
Graph drawing
Planar graph
IR-74738

Access to Document

10.1016/S0167-6377(02)00119-0

Cite this

@article{0f9c9cb09a994154b4e696d4bf6f0b53,

title = "Embeddings of planar graphs that minimize the number of long face cycles",

abstract = "We consider the problem of finding embeddings of planar graphs that minimize the number of long-face cycles. We prove that for any k≥4, it is NP-complete to find an embedding that minimizes the number of face cycles of length at least k.",

keywords = "METIS-208617, Computational Complexity, Graph drawing, Planar graph, IR-74738",

author = "Gerhard Woeginger",

year = "2002",

doi = "10.1016/S0167-6377(02)00119-0",

language = "English",

volume = "30",

pages = "167--168",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Embeddings of planar graphs that minimize the number of long face cycles

AU - Woeginger, Gerhard

PY - 2002

Y1 - 2002

N2 - We consider the problem of finding embeddings of planar graphs that minimize the number of long-face cycles. We prove that for any k≥4, it is NP-complete to find an embedding that minimizes the number of face cycles of length at least k.

AB - We consider the problem of finding embeddings of planar graphs that minimize the number of long-face cycles. We prove that for any k≥4, it is NP-complete to find an embedding that minimizes the number of face cycles of length at least k.

KW - METIS-208617

KW - Computational Complexity

KW - Graph drawing

KW - Planar graph

KW - IR-74738

U2 - 10.1016/S0167-6377(02)00119-0

DO - 10.1016/S0167-6377(02)00119-0

M3 - Article

SN - 0167-6377

VL - 30

SP - 167

EP - 168

JO - Operations research letters

JF - Operations research letters

IS - 3

ER -

Embeddings of planar graphs that minimize the number of long face cycles

Abstract

Keywords

Access to Document

Fingerprint

Cite this