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

Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)167-168
JournalOperations research letters
Volume30
Issue number3
DOIs
Publication statusPublished - 2002

Keywords

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

Fingerprint Dive into the research topics of 'Embeddings of planar graphs that minimize the number of long face cycles'. Together they form a unique fingerprint.

Cite this