Πάχος Γραφήματος Και Παραλλαγές, Πάχος Σχεδίασης Γραφήματος, Πολυπλοκότητα

Abstract

Θα αναφερθούμε σε προβλήματα που αφορούν τη σχεδίαση γραφημάτων σε επίπεδα, τα οποία συνήθως βρίσκουν εφαρμογές στα \textlatin{VLSI} κυκλώματα και την απεικόνιση των γραφημάτων. Παρουσιάζουμε μια εναλλακτική ώθηση για τη μελέτη της σχεδίασης γραφημάτων από το πεδίο της διαχείρησης της εναέριας κυκλοφορίας και ειδικότερα τα πρότυπα που προκύπτουν από (ή φαίνονται ως) πτήσεις σε ευθεία μεταξύ αεροδρομίων ή σημείων διέλευσης. Εισάγουμε το πάχος σχεδίασης (\textlatin{$\vartheta$}) της σχεδίασης $D$ ενός γραφήματος ως \emph{τον ελάχιστο αριθμό επιπέδων στα οποία μπορούμε να διαχωρίσουμε τις ακμές μιας (αναλλοίωτης) σχεδίασης γραφήματος, έτσι ώστε μέσα σε ένα επίπεδο οι ακμές να μη διασταυρώνονται}, και συζητάμε για τις καλά μελετημένες έννοιες του πάχους γραφήματος (\textlatin{$\theta$}), του γεωμετρικού πάχους ($\bar\theta$) και του πάχους εμφύτευσης σε βιβλίο ($bt$). Εξερευνούμε την ιστορία και σημαντικά αποτελέσματα για το πάχος γραφήματος και το γεωμετρικό πάχος γραφήματος, συμπεριλαμβανομένων των ιδιοτήτων του πάχους του $K_n$ και του $K_{m,n}$. Βασιζόμενοι στον ορισμό του πάχους εμφύτευσης σε βιβλίο που χρησιμοποιεί μια κυρτή εμφύτευση των κορυφών του γραφήματος στο επίπεδο, επικεντρονώμαστε στις κυρτές σχεδιάσεις $D_{conv}$ ενός γραφήματος και παρουσιάζουμε μερικές ιδιότητες, μεταξύ άλλων και για να αποδείξουμε εκ νέου ότι $bt(K_n)=\vartheta(D_{conv}(K_n))= \lceil \frac{n}{2} \rceil$. Προχωρώντας στις αυθαίρετες σχεδιάσεις του γραφήματος $G$, ισχυριζόμαστε πως $\vartheta(K_n) \leq \lceil \frac{n}{2} \rceil$ για κάθε σχεδίαση. Στο τελευταίο κεφάλαιο που αφορά στην πολυπλοκότητα, ορίζουμε μια οικογένεια προβλημάτων που αφορούν το πάχος γραφήματος, δίνοντας ιδιαίτερη προσοχή στο αντίστοιχο ως προς τη δουλειά μας πρόβλημα χρωματισμού: \emph{<<Δοσμένης μιας σχεδίασης ενός γραφήματος, μπορούν οι ακμές του να διαχωριστούν σε $k$ επίπεδα>>}? Χρησιμοποιούμε τα \textlatin{SEG} γραφήματα, τα γραφήματα τομής ενός συνόλου ευθυγράμμων τμημάτων στο επίπεδο, και την κλάση-υποσύνολο των \textlatin{circle} γραφημάτων για να δείξουμε ότι το πρόβλημα είναι \textlatin{\emph{NP}-complete} τόσο για μια τυχαία $k\geq 3$, όσο και για μια κυρτή σχεδίαση $k= 3$, αποδεικνύοντας στην πορεία ότι τα \textlatin{CROSS} γραφήματα, τα γραφήματα διασταύρωσης ευθυγράμμων τμημάτων, συμπίπτουν με τα \textlatin{SEG} γραφήματα. Τέλος, αναφερόμαστε σε 3 προβλήματα ύπαρξης τριγωνοποίησης για μια σχεδίαση γραφήματος, \textlatin{\emph{TRI, poly-TRI}} και \textlatin{\emph{convex TRI}}, που αφορούν κατ' αντιστοιχία στην τριγωνοποίηση συνόλου σημείων, την τριγωνοποίηση πολυγώνου και την τριγωνοποίηση κυρτού πολυγώνου (ή κυρτού συνόλου σημείων). Παρουσιάζουμε μια παραλλαγή της κλάσης των \textlatin{SEG} γραφημάτων, την \textlatin{SEG$_h$}, για να αναπαράγουμε ότι το πρόβλημα \textlatin{\emph{TRI}} είναι \textlatin{\emph{NP}-complete}, ενώ διαμέσου των \textlatin{circle} γραφημάτων, το πρόβλημα \textlatin{\emph{convex TRI}} είναι στο $P$.