Direkt zum Inhalt

Lexikon der Mathematik: Buchdicke

minimale ganze Zahl k, für die ein Graph G eine kreuzungsfreie Einbettung \({G}^{^{\prime} }\) in ein k-Buch besitzt, bei der jede Ecke auf dem Rücken des Buches liegt und jede Kante in genau einer Seite des Buches enthalten ist.

Dabei ist ein k-Buch der topologische Raum, der durch die Identifizierung von jeweils einer Seite in k verschiedenen Einheitsquadraten (versehen mit der üblichen Topologie) zu einer einzigen Seite entsteht, die man den Rücken des Buches nennt. Die k Einheitsquadrate heißen die Seiten des Buches.

Die Bestimmung der Buchdicke eines Graphen ist ein sehr schwieriges Problem, und nur für wenige spezielle Graphenklassen ist die Buchdicke bekannt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos