εθνικο μετσο βιο πολυτεχνει ο

Transcript

Εθνικο Μετσο βιο Πολυτεχνει ο Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών Τομέας Μαθηματικών Διπλωματικη Εργασι α Σχεδίαση και Ανάπτυξη Εφαρμογής Αρμόδιας για τη Μελέτη του Προβλήματος του Book Embedding Επιμέλεια: Δε σποινα Παπαθεοδω ρου Επιβλέπων: Αντω νιος Συμβω νης 16 Οκτωβρι ου 2015 2 2 Εθνικο Μετσο βιο Πολυτεχνει ο Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών Τομέας Μαθηματικών Διπλωματικη Εργασι α Σχεδίαση και Ανάπτυξη Εφαρμογής Αρμόδιας για τη Μελέτη του Προβλήματος του Book Embedding Εγκρίθηκε από την τριμελή εξεταστική επιτροπή:... Αντω νιος Συμβω νης καθηγητη ς ΕΜΠ... Ιωα ννης Κολε τσος Επι κουρος Καθηγητη ς ΕΜΠ... Πε τρος Στεφανε ας Λε κτορας ΕΜΠ 16 Οκτωβρι ου 2015 2 2 στη Μητε ρα μου 4 4 Abstract The power of mathematics is often to change one thing into another, to change geometry into language. Marcus du Sautoy A k-pages book embedding is a drawing of a graph in a book, placing all the vertices along the spine of the book and drawing the edges in k pages of the book so that edges on the same page do not cross. The theory of Book Embeddings has a diversity of applications like the fault-tolerant computing VLSI design [CLR87], where vertices correspond to circuit s parts and edges to their connections. Others applications include parallel computing, graph seperators [GKS89], software complexity metrics, vehicle traf ic engineering,bio-informatics [HS99], and others. Despite the wide use of book embeddings there is no available software tool, that is user friendly and easily expandable in order to support research in this ield. So, the subject of this diploma thesis is the analysis, design and development of such a tool. Top priority was given to write a well-structured and easily manageable code, which enables further extension and enrichment. The user can easily add more algorithms or features. Keywords graph theory, graph, planarity, book embedding, crossings,page number, Java 5 6 6 Περίληψη The power of mathematics is often to change one thing into another, to change geometry into language. Marcus du Sautoy Μια k-σε λιδη εμφυ τευση σε βιβλι ο ενο ς γραφη ματος ει ναι η απεικο νιση του γραφη ματος σε ε να βιβλι ο, ο που ο λες οι κορυφε ς του γραφη ματος θα τοποθετηθου ν πα νω στην ρα χη και οι ακμε ς σε k σελι δες του βιβλι ου ε τσι ω στε να μην δημιουργου - νται διασταυρω σεις. Η εμφυ τευση σε βιβλι ο βρι σκει ποικι λες εφαρμογε ς ο πως ο ανεκτικο ς σε σφα λ- ματα σχεδιασμο ς VLSI (fault-tolerant computing VLSI design) [CLR87] ο που οι κορυφε ς του γραφη ματος αντιστοιχου ν στα τμη ματα ενο ς κυκλω ματος και οι ακμε ς αντιστοιχου ν στις συνδε σεις μεταξυ τους. Άλλες περιοχε ς εφαρμογω ν των εμφυτευ - σεων σε βιβλι ο περιλαμβα νουν παράλληλο προγραμματισμό (parallel computing), graph seperators [GKS89], μετρικε ς πολυπλοκο τητας λογισμικου (software complexity metrics), σχεδι αση κι νησης οχημα των (vehicle traffic engineering), βιοπληροφορική(bioinformatics) [HS99] και πολλε ς α λλες. Παρ ο λη ο μως την χρησιμο τητα της μελε της των εμφυτευ σεων δεν υπα ρχει ακο μη ε να εργαλει ο με φιλικο προς το χρη στη γραφικο περιβα λλον κατα λληλο για να διευκολυ νει την ε ρευνα στον τομε α αυτο. Σκοπο ς, επομε νως, αυτη ς της διπλωματικη ς εργασι ας ει ναι η ανα πτυξη λογισμικου σε java το οποι ο θα καλυ πτει το υπα ρχων κενο. Έχει δοθει ιδιαι τερη ε μφαση ε τσι ω στε το εργαλει ο αυτο να ει ναι ο σο το δυνατο ν πιο ευ χρηστο και λειτουργικο γι νεται, αλλα και ευε λικτο ε τσι ω στε να μπορει να επεκταθει με ενσωμα τωση περισσο τερων αλγορι θμων και επιλογω ν. Λέξεις Κλειδιά Θεωρι α Γραφημα των, γρα φημα, επιπεδο τητα, εμφυ τευση σε βιβλι ο, διασταυρω - σεις, σελιδα ριθμος, Java 7 8 8 Ευχαριστίες Η εργασι α αυτη αποτελει αποτε λεσμα επι πονης και επι μονης προσπα θειας για την απο κτηση του διπλω ματος απο τη σχολη Εφαρμοσμε νων Μαθηματικω ν. Θα η θελα λοιπο ν να ευχαριστη σω ο λους ο σους συνε λαβαν στην ανα πτυξη της. Αρχικα, θε λω να εκφρα σω τις θερμε ς ευχαριστι ες μου στον καθηγητη μου κ. Αντω - νιο Συμβω νη για την ευκαιρι α που μου ε δωσε να ασχοληθω με ε να το σο ενδιαφε ρον θε μα αλλα και την εμπιστοσυ νη που με ε δειξε σε ο λη τη δια ρκεια περα τωσης της. Επι σης, θα η θελα να τον ευχαριστη σω για την συνεισφορα του, ο λα αυτα τα χρο νια ως δα σκαλος, καθω ς με ε κανε να αγαπη σω την Πληροφορικη και να ακολουθη σω τον κλα δο αυτο ν. Θα η θελα, επι σης, να ευχαριστη σω ιδιαι τερα την Διδα κτορα Εφαρμοσμε νη Μαθηματικο. Χρυσα νθη Ραυτοπου λου, για την εμψυχωτικη καθοδη γηση και τη συνεχη υποστη ριξη της σε ο λα τα στα δια και επι πεδα διεκπεραι ωσης της εργασι ας. Οι χρη - σιμες συμβουλε ς και παρατηρη σεις της υπη ρξαν πολυ τιμες αλλα και τε λος, για τις ευχα ριστες ω ρες που περα σαμε μαζι στο γραφει ο. Τε λος, ευχαριστω θερμα την οικογε νεια μου για την υποστη ριξη τους ο λα τα χρο νια της μαθητικη ς και φοιτητικη ς μου ζωη ς και για ο λα ο σα μου προ σφεραν ο πως και το Στρα το που πα ντα με στηρι ζει, με εμψυχω νει και με εμπνε ει. 9 10 10 Περιεχόμενα Περιεχόμενα 11 1 Εισαγωγικές Έννοιες Της Θεωρίας Γραφημάτων Γενικοι Ορισμοι Απεικο νιση γραφημα των στο επι πεδο Κριτη ρια Επιπεδο τητας Το προ βλημα της εμφυ τευσης γραφη ματος σε βιβλι ο -The Book Embedding Problem Τοπολογικο book embedding Ιστορικα Στοιχει α Ανάλυση και Σχεδιασμός Σχεδιασμο ς Εργαλει α Υλοποίηση bee.algo Crossings public class Heuristic bee.view public class BeeGui public class EditView public class HelpFrame public class MyGraph2DView public class MyMoveSelectionMode public class MyPopupMode public class MyPopUpMode2 extends PopupMode public class MyZoomWheelListener bee.option.options 12 ΠΕΡΙΕΧΟΜΕΝΑ public class Utilities bee.option public class EdgePropertyHandler public class MyEditModeConstraint public class MyEditModeFree public class MyEditModeLooseConstraint bee.demo.graphtemplate public class EmbeddedGraph bee.layout public class MySimpleLayouter bee.io public class BEIOhandler bee.demo public class Main public interface Changeable public class NodeMoveChange public class EdgeMoveChange public class ChangeManager public class MainControler public class LVControler wrapper public class BEWrapper Η Εφαρμογή Bee Άνοιγμα Γραφη ματος Επιλογε ς και Επεξεργασι α Δημιουργι α του Εμφυτευμε νου Γραφη ματος και Επεξεργασι α Ευρετικοι Με θοδοι Συμπεράσματα και Μελλοντικές Επεκτάσεις 53 6 Παράρτημα: Κώδικας της Εφαρμογής Bee 55 Βιβλιογραφία 77 12 1 Εισαγωγικές Έννοιες Της Θεωρίας Γραφημάτων God used beautiful mathematics in creating the world. Paul Dirac 1.1 Γενικοί Ορισμοί Γράφημα (graph) καλει ται ε να διατεταγμε νο ζευ γος G = (V, E) ο που V ει ναι ε να πεπερασμε νο συ νολο και E ε να συ νολο υποσυνο λων του V το καθε να εκ των οποι ων ε χει δυ ο στοιχει α του V. Τα στοιχει α του V καλου νται κορυφε ς του G και τα στοιχει α του E ακμε ς του G. Έστω γρα φημα G = (V, E). Αν το συ νολο των ακμω ν του E ει ναι ε να συ νολο απο μη διατεταγμε να ζευ γη {u, v το τε το G ονομα ζεται μη κατευθυνόμενο γρα - φημα. Διαφορετικα ονομα ζεται κατευθυνόμενο (directed). Σε αυτη την περι πτωση η ακμη e = {u, v ει ναι εισερχο μενη ακμη για την κορυφη v και εξερχο μενη για την κορυφη u. Μια ακολουθι α απο εναλλασσο μενες κορυφε ς και ακμε ς του γραφη ματος χωρι ς επαναλαμβανο μενες κορυφε ς ονομα ζεται μονοπάτι (path). Ένα μονοπα τι με ταυτο σημα τερματικα σημει α ονομα ζεται κύκλος (cycle). Ένα γρα φημα καλει ται συνεκτικό (connected) (η απλα συνεκτικο ) ο ταν για κα θε ζευ γος κορυφω ν του x, y V (G) υπα ρχει (x, y)-μονοπα τι στο G. Διαφορετικα ονομα ζεται μη συνεκτικο. Συνεκτικές συνιστώσες (connencted components) ενο ς γραφη ματος G ονομα ζονται τα με γιστα συνεκτικα υπογραφη ματα του. Έστω ε να συνεκτικο γρα φημα G και ε στω ε να συ νολο S V (G). Το συ νολο S ει ναι διαχωριστής του G αν το γρα φημα G S δεν ει ναι συνεκτικο. Ένας διαχωριστη ς λε γεται ελάχιστος αν δεν υπα ρχει α λλος διαχωριστη ς του G με μικρο τερο με γεθος. Ένα γρα φημα G με V (G) 2 ονομα ζεται δισυνεκτικό (2-connected) αν ο λοι οι διαχωριστε ς του ε χουν με γεθος 2. Ένας 3-κυ κλος του γραφη ματος, ο οποι ος αν αφαιρεθει αποσυνδε ει το γρα φημα ονομα ζεται separating Triangle. Ένα γρα φημα το οποι ο ει ναι συνεκτικο και α κυκλο ονομα ζεται δέντρο (tree). Ένα μη συνεκτικο γρα φημα χωρι ς κυ κλους ονομα ζεται δάσος (forest). Οι συνεκτι- 13 14 Κεφάλαιο 1. Εισαγωγικές Έννοιες Της Θεωρίας Γραφημάτων κε ς συνιστω σες ενο ς δα σους ει ναι δε ντρα. Ένα γρα φημα H καλει ται επαγόμενο (induced) υπογρα φημα του G εα ν V (H) V (G) και u, v V (H), { u, v E(H) {u, v E(G) Δυ ο γραφη ματα ει ναι ομοιομορφικά (homeomorphic) ο ταν μπορει να παραχθει το ε να απο το α λλο με μια η περισσο τερες υποδιαιρε σεις ακμω ν και συμπτυ ξεις κορυφω ν. Δυ ο γραφη ματα G, H, καλου νται ισόμορφα αν υπα ρχει μια 1 1 και επι απεικο νιση σ : V (G) V (H) τε τοια ω στε x, y V (G) με x y, ισχυ ει ο τι {x, y E(G) {σ(x), σ(y) E(H). Αν δυ ο γραφη ματα G και H ει ναι ισομορφικα χρησιμοποιου με το συμβολισμο G H. Η σχε ση ει ναι σχε ση ισοδυναμι ας. Άρα ε να γρα φημα μπορει να ει ναι ισο μορφο με α πειρα το πλη θος γραφη ματα που ανη κουν στην ι δια κλα ση ισοδυναμι ας. Για κα θε θετικο ακε ραιο r 0 ορι ζεται το γρα φημα K r = ({u 1,..., u r, {{u i, u j 1 i j r) το οποι ο ονομα ζεται κλίκα (clique) η r-κλι κα. Ένα γρα φημα G με r κορυφε ς καλει ται πλήρες αν G K r. Για κα θε ζευ γος θετικω ν ακεραι ων p, q 0 ορι ζεται το γρα φημα K p,q = (A B, E) ε τσι ω στε A = {u 1,..., u p, B = {v 1,..., v q, E = {{u i, v j 1 i p και 1 j q. Τα A, B ει ναι ανεξα ρτητα συ νολα και το K p,q ονομα ζεται πλήρες διμερές (bipartite) γρα φημα. Έστω γρα φημα G. Ένας κυ κλος του G ο οποι ος διε ρχεται απο ο λες τις κορυφε ς του G ονομα ζεται κύκλος Hamilton. Ένα γρα φημα το οποι ο περιε χει ε ναν κυ κλο Hamilton ονομα ζεται Hamiltonian γράφημα. Ένα γρα φημα ονομα ζεται υποχαμιλτόνιο (subhamiltonian graph) αν ει ναι υπογρα φημα ενο ς επι πεδου χαμιλτο νιου γραφη ματος. Ένα κυκλικο γρα φημα (cycle graph η circular graph, C n ) ει ναι ε να γρα - φημα το οποι ο αποτελει ται απο ε ναν κυ κλο. 1.2 Απεικόνιση γραφημάτων στο επίπεδο Αν ε να γρα φημα μπορει να απεικονιστει στο επι πεδο ου τως ω στε οι γραμμε ς που αντιστοιχου ν στις ακμε ς του να τε μνονται μο νο πα νω στις κορυφε ς που αποτελου ν τα α κρα τους, το τε ει ναι ε να επίπεδο (planar) γρα φημα. Ένα επι πεδο γρα - φημα G, μαζι με την απεικο νιση του στο επι πεδο καλει ται επίπεδη εμφύτευση (planar embedding) του G. Ένα επι πεδο γρα φημα G λε γεται μεγιστικο ( triangulated η maximal planar) αν η προ σθεση οποιασδη ποτε ακμη ς στο G δημιουργει ε να μη επι πεδο γρα φημα (nonplanar graph). Μι α επι πεδη εμφυ τευση του G χωρι ζει το R 2 σε περιοχε ς, οι οποι ες ονομα ζονται όψεις (faces) του G. Μι α απο αυτε ς τις ο ψεις ει ναι μη φραγμε νη και ονομα ζεται 14 1.2 Απεικόνιση γραφημάτων στο επίπεδο 15 εξωτερικη ο ψη (exterior face). Αν για ε να επι πεδο γρα φημα G υπα ρχει επι πεδη εμφυ τευση, τε τοια ω στε κα θε κορυφη του να βρι σκεται στην εξωτερικη ο ψη, το τε το G ει ναι εξωεπίπεδο (outerplanar). Παρατήρηση 1.1. Ενα γράφημα που είναι εμφυτεύσιμο στο επίπεδο είναι εμφυτεύσιμο και σε μια σφαίρα. Ισχύει και το αντίστροφο. Έστω γρα φημα G και F (G) το συ νολο των ο ψεων του G, το γρα φημα G το οποι ο ε χει ως V (G ) = {f : f F (G) και E(G ) = {e = {f, g : f, g F (G) ονομα ζεται δυικό γράφημα (dual) του G. Θεώρημα 1.2 (Euler-1970). Έστω G συνεκτικό επίπεδο γράφημα με n κορυφές, m ακμές και f όψεις. Τότε ισχύει: n + f = m + 2. Θεώρημα 1.3. Έστω επίπεδο γράφημα G με n κορυφές και m ακμές. Τότε m 3n 6. Ειδικα για τα διμερη γραφη ματα ισχυ ει: Θεώρημα 1.4. Έστω διμερές επίπεδο γράφημα G με n κορυφές και m ακμές. Τότε m 2n 4. Παρατήρηση 1.5. Αποδεικνύεται (εύκολα, με χρήση των παραπάνω θεωρημάτων) ότι τα γραφήματα K 5 και K 3,3 δεν είναι επίπεδα. Θεώρημα 1.6 ( Wagner-1937, Fary-1948). Κάθε επίπεδο γράφημα μπορεί να απεικονισθεί στο επίπεδο έτσι ώστε οι ακμές του να αντιστοιχούν σε ευθύγραμμα τμήματα Κριτήρια Επιπεδότητας Υπα ρχουν αρκετα κριτη ρια για την επιπεδο τητα των γραφημα των. Ο Πολωνο ς μαθηματικο ς Kazimierz Kuratowski προσδιο ρισε τα επι πεδα γραφη ματα χρησιμοποιω ντας τον χαρακτηρισμο των απαγορευμε νων γραφημα των ενω ο Αμερικα νος Hassler Whitney προσδιορι σε την επιπεδο τητα βα ση της υ παρξης του αλγεβρικου δυικου. Θεώρημα 1.7 ( Kuratowski-1930). Ένα γράφημα G είναι επίπεδο αν και μόνο αν κανένα υπογράφημά του δεν είναι ομοιμορφικό με το K 5 ή το K 3,3. 15 16 Κεφάλαιο 1. Εισαγωγικές Έννοιες Της Θεωρίας Γραφημάτων Ορισμός. Ως Matroid ορι ζεται ε να ζευ γος (E, I) ο που E ει ναι ε να πεπερασμε νο συ - νολο και I μια οικογε νεια υποσυνο λων του E που καλου νται ανεξα ρτητα συ νολα (independent sets) για το οποι ο ικανοποιου νται οι ιδιο τητες: i) A A E αν A I το τε A I ii) Αν I 1 και I 2 ανεξα ρτητα συ νολα και I 2 I 1, το τε για κα ποιο x I 2 I 1, το συ νολο I 1 {x ει ναι ανεξα ρτητο. Θεώρημα 1.8 ( Whitney-1932). Ένα γράφημα G είναι επίπεδο αν και μόνο αν υπάρχει ένα γράφημα F τέτοιο ώστε M(G) = M (F ). 1.3 Το πρόβλημα της εμφύτευσης γραφήματος σε βιβλίο -The Book Embedding Problem Η εμφυ τευση γραφη ματος σε σελι δα ει ναι μια ειδικη περι πτωση εμφυ τευσης επι πεδου γραφη ματος. Πιο συγκεκριμε να: Η εμφύτευση σε σελίδα (page embedding) ενο ς γραφη ματος G = (V, E) ει ναι μια επι πεδη εμφυ τευση του G τε τοια ω στε οι κορυφε ς του G τοποθετου νται πα νω στον α ξονα του R και κα θε ακμη απεικονι ζεται ως κυκλικο το ξο στο α νω ημιεπι πεδο {(x, y) R 2 : y 0 εκτο ς απο τα α κρα της (endpoints). Ένα k-σε λιδο βιβλι ο ει ναι μια δομη που αποτελει ται απο μια ευθει α, αναφερο μενη ως ρα χη (spine) του βιβλι ου, και απο k ημιεπι πεδα, αναφερο μενα ως σελι δες του βιβλι ου, που ε χουν τη ρα χη ως κοινο τους συ νορο. Μια εμφύτευση σε βιβλίο (book embedding) ενο ς γραφη ματος G ορι ζεται ως μια απεικο νιση του G τε τοια ω στε οι κορυφε ς του G να απεικονι ζονται πα νω στη ρα χη του βιβλι ου, ενω κα θε ακμη απεικονι ζεται ως κυκλικο το ξο πα νω σε μια σελι δα του βιβλι ου, και οι ακμε ς που ανη κουν στην ι δια σελι δα δεν τε μνονται μεταξυ τους. Πάχος (book thickness) η σελιδάριθμος (page number) ενο ς γραφη ματος G ορι ζεται ως ο ελα χιστος ακε ραιος k ε τσι ω στε το G να επιδε χεται μια εμφυ τευση σε k-σε λιδο βιβλι ο. Άνω φράγματα Εμφυτεύσεων Κα θε γρα φημα επιδε χεται εμφυ τευση σε βιβλι ο. Πιο συγκεκριμε να για ε να γρα - φημα με με n κορυφε ς το το πα χος εμφυ τευσης φρα σσεται απο την ποσο τητα n/2. Για πλη ρη γραφη ματα το φρα γμα ει ναι αυστηρο [BK79] ενω για τα πλη ρη διμερη K n,m, με n m το πα χος εμφυ τευσης σε βιβλι ο ει ναι το πολυ ι σο με n και αν m n(n 1) ει ναι ακριβω ς ι σο με n [BK79, dkps14]. 16 1.3 Το πρόβλημα της εμφύτευσης γραφήματος σε βιβλίο -The Book Embedding Problem 17 Έχει αποδειχτει ο τι το πα χος εμφυ τευσης σε βιβλι ο ενο ς γραφη ματος ισου ται με το με γιστο πα χος εμφυ τευσης σε βιβλι ο των δισυνεκτικω ν του συνιστωσω ν [BK79], επομε νως μπορου με πα ντα να υποθε τουμε ο τι το γρα φημα ει ναι δισυνεκτικο. Άνω φρα γματα στο πα χος εμφυ τευσης σε βιβλι ο ε χουν επι σης συσχετιστει με δια φορες αναλλοίωτες ιδιότητες(invariants) γραφημα των. Για παρα δειγμα τα γραφη ματα με m ακμε ς ε χουν πα χος εμφυ τευσης σε βιβλι ο O( m) [Mal94]. Εμφυτεύσεις επίπεδων γραφημάτων σε βιβλίο Η κατηγορι α γραφημα των που ε χει μελετηθει περισσο τερο στο παρελθο ν ως προς τις εμφυτευ σεις σε βιβλι ο ει ναι η κατηγορι α των επι πεδων γραφημα των. Το πλε ον δημοφιλε ς και κεντρικο αποτε λεσμα σχετικα με εμφυτευ σεις επι πεδων γραφημα των σε βιβλι ο οφει λεται στον Μ. Γιαννακα κη [Yan89], ο οποι ος απε δειξε στα τε λη της δεκαετι ας του 80 ο τι τα επι πεδα γραφη ματα ε χουν πα χος εμφυ τευσης σε βιβλι ο το πολυ τε σσερα. Ανοιχτο ερω τημα παραμε νει αν το α νω φρα γμα των τεσσα - ρων σελι δων ει ναι αυστηρο. Ειδικε ς περιπτω σεις επι πεδων γραφημα των μπορου ν να εμφυτευ του ν σε βιβλι ο με λιγο τερες σελι δες: για παρα δειγμα αποδεικνυ εται ο τι τα επι πεδα 3-δένδρα (3- trees) εμφυτευ ονται σε βιβλι ο με 3 σελι δες ( Heath [Hea84]). Επι σης, τα εξωεπίπεδα (outerplanar) γραφη ματα ε χουν πα χος εμφυ τευσης σε βιβλι ο 1 ενω η κλα ση των εμφυτευ σιμων γραφημα των σε βιβλι ο με 2 σελι δες ταυτι ζεται με την κλα ση των υποχαμιλτόνιων (subhamiltonian) γραφημα των (βλ. Εικο να 1.1i, 1.1ii). Η συσχε τιση υποχαμιλτο νιων κυ κλων και εμφυτευ σεων σε βιβλι ο δυ ο σελι δων προκυ πτει α μεσα αν υποθε σουμε ο τι η σειρα των κορυφω ν κατα μη κος της ρα χης ισοδυναμει με την σειρα που εμφανι ζονται πα νω στον υποχαμιλτο νιο κυ κλο. Οι ακμε ς διαχωρι ζονται σε δυ ο σελι δες βα ση του εα ν βρι σκονται στο εσωτερικο του κυ - κλου η ο χι. Υπα ρχουν ο μως και επι πεδα γραφη ματα τα οποι α δεν ει ναι υποχαμιλτο νια: για παρα δειγμα το γρα φημα των Goldner-Harary (βλ. Εικο να 1.1iii) (i) (ii) (iii) Εικόνα 1.1: (a) Ένα υποχαμιλτο νιο γρα φημα G. (b) Εμφυ τευση του G σε βιβλι ο 2 σελι δων. (c) Το γρα φημα των Goldner-Harary. 17 18 Κεφάλαιο 1. Εισαγωγικές Έννοιες Της Θεωρίας Γραφημάτων Κλάσεις γραφημάτων που είναι γνωστό ότι είναι υποχαμιλτόνιες: Κα θε maximal planar γρα φημα χωρι ς separatingtriangles ει ναι χαμιλτόνιο (hamiltonian) (Whitney [Whi31]). Ο Tutte [Tut56] ε δειξε ο τι κα θε 4-συνεκτικο επι πεδο γρα φημα περιε χει ε να Χα μιλτον κυ κλο και οι Chiba και Nishizeki [CN89] περιε γραψαν ε ναν αλγο ριθμο γραμμικου χρο νου για την ευ ρεση ενο ς Χα μιλτον κυ κλου σε ε να 4-συνεκτικο επι πεδο γρα φημα. Κα θε maximal planar γρα φημα με τουλα χιστον πε ντε κορυφε ς και χωρι ς separating Triangles ει ναι 4-συνεκτικο (Chen [Che03]) και κα θε 4-συνεκτικο επι πεδο γρα φημα ε χει Χα μιλτον κυ κλο που περιε χει δυ ο αυθαι ρετες ακμε ς του γραφη ματος (Sanders [San97]). Επιπλε ον, κα θε επι πεδο γρα φημα (ο χι απαραι τητα maximal) χωρι ς separating Triangles ει ναι υποχαμιλτο νιο ( [KO07]). Τε λος, εα ν ε να maximal planar περιε χει μο νο δυ ο τε τοια τρι γωνα, το τε ει ναι χαμιλτο νιο (Helden [Hel07]). Για επι πεδα γραφη ματα μικρου με γιστου βαθμου, ο Heath [Hea85] ε δειξε ο τι κα θε επι πεδο γρα φημα γρα φημα με γιστου βαθμου 3 ει ναι υποχαμιλτο νιο, και αργο τερα οι Μπε κος και α λλοι απε δειξαν ο τι και τα επι πεδα γραφη ματα με γιστου βαθμου 4 ει ναι υποχαμιλτο νια και συνεπω ς εμφυτευ ονται σε 2 σελι δες (με αλγο ριθμο τετραγωνικου χρο νου) [BGR14]. Τε λος, οι Μπε κος και α λλοι απε δειξαν ο τι κα θε 1-επι πεδο γρα φημα (δηλαδη ε να γρα φημα το οποι ο απεικονι ζεται στο επι πεδο ω στε κα θε ακμη να διασταυρω νεται το πολυ μι α φορα ) επιδε χεται μια εμφυ τευση σε βιβλι ο με σταθερο αριθμο σελι δων [BBKR15]. Πολυπλοκότητα Η ευ ρεση ενο ς υποχαμιλτο νιου κυ κλου ει ναι NP-complete προ βλημα [Wig82]. Συνεπω ς, ο υπολογισμο ς του πα χους εμφυ τευσης ενο ς γραφη ματος σε βιβλι ο ει ναι NPhard. Εα ν η σειρα των κορυφω ν κατα μη κος της ρα χης δι νεται, το τε, εα ν υπα ρχει, μια εμφυ τευση σε βιβλι ο δυ ο σελι δων μπορει να υπολογιστει σε γραμμικο χρο νο, εφο σον το προ βλημα ανα γεται στο προ βλημα ελε γχου επιπεδο τητας. Για τρεις σελι δες, υπα ρχει μια πολυωνυμικου χρο νου διαδικασι α ο μως για τε σσερις η περισσο τερες σελι δες, το προ βλημα ει ναι NP-hard [Ung88, GJMP80]. Επομε νως δεν μπορου με να ευελπιστου με στην υ παρξη αποδοτικου αλγορι θμου για την επι λυση του. 18 1.4 Τοπολογικό book embedding Τοπολογικό book embedding Σε μια τοπολογικη εμφυ τευση βιβλι ου ενο ς γραφη ματος, το γρα φημα ζωγραφι ζεται σε ε να τοπολογικο βιβλι ο τοποθετω ντας τις κορυφε ς πα νω στη ρα χη του βιβλι ου και τοποθετω ντας τις ακμε ς πα νω στις σελι δες, επιτρε ποντας ο μως στις ακμε ς να τε μνουν τη ρα χη. Έχει δειχθει ο τι κα θε γρα φημα με n κορυφε ς και m ακμε ς μπορει να εμφυτευθει σε 3 σελι δες [BDGL08] ενω ε να επι πεδο γρα φημα σε 2 σελι δες με το πολυ μι α τομη με τη ρα χη για κα θε ακμη [GLMS07]. Σε μια τοπολογικη εμφυ τευση επιδιω κουμε να ελαττω σουμε τον αριθμο των τομω ν με τη ρα χη. 1.5 Ιστορικά Στοιχεία Ενδεικτικα για λο γους πληρο τητας αναφε ρουμε και κα ποια ιστορικα στοιχει α. Η ε ννοια του βιβλι ου ορι στηκε απο τους C. A. Persinger και Gail Atneosen τη δεκαετι α του Ο Atneosen η δη αποδεχο ταν την εμφυ τευση γραφημα των σε βιβλι α αλλα η επι σημη ιδε α (concept) μια εμφυ τευσης σε βιβλι ο δ