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.
Schreiben Sie uns!