Γραμμικές απεικονίσεις γραφημάτων με διπλοτόξα
Φόρτωση...
Ημερομηνία
Συγγραφείς
Βελισσάρης, Γεώργιος
Velissaris, Georgios
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Στην παρούσα διατριβή εισάγουμε και μελετάμε μία νέα παραλλαγή γραμμικών
απεικονίσεων γραφημάτων σύμφωνα με την οποία οι κορυφές του γραφήματος δια-
τάσσονται κατά μήκος μιας ευθείας γραμμής, η οποία συχνά αναφέρεται ως ράχη,
ενώ οι ακμές του γραφήματος διαμερίζονται σε σύνολα, τα οποία ονομάζονται σε-
λίδες. Στην παραλλαγή που μελετάμε: (i) κάθε σελίδα αντιστοιχεί σε ένα διακριτό
επίπεδο που περιέχει τη ράχη, (ii) κάθε ακμή απεικονίζεται είτε ως ημικύκλιο άνω-
θεν ή κάτωθεν της ράχης είτε ως δύο ημικύκλια εκατέρωθεν της ράχης τα οποία
έχουν ένα κοινό σημείο που βρίσκεται στη ράχη και ανάμεσα στα δύο άκρα της
ακμής και (iii) κάθε δύο ακμές της ίδιας σελίδας δεν τέμνονται. Αναφερόμαστε σε
τέτοιες γραμμικές απεικονίσεις ως μονότονες με διπλοτόξα. Δοθέντος ενός γρα-
φήματος G, το ενδιαφέρον μας εστιάζει στον ελάχιστο αριθμό bn(G) σελίδων που
απαιτούνται για την ύπαρξη μίας γραμμικής απεικόνισης με μονότονα διπλοτόξα.
Αποδεικνύουμε ότι για το πλήρες γράφημα Kn ισχύει bn(Kn) ≤ n
4
. Το
αποτέλεσμα αυτό επιτυγχάνεται μέσω μίας γενικής κατασκευής που αποδίδει δια-
φορετικές γραμμικές απεικονίσεις με μονότονα διπλοτόξα, στα οποία ο αριθμός
των ακμών, που απεικονίζονται ως διπλοτόξα, μπορεί να κυμαίνεται από 0 έως
n2
8 − n
4 +2. Για το πλήρες διμερές γράφημα Kn,n δείχνουμε ότι bn(Kn,n) ≤ n
3
+1
στην περίπτωση που οι κορυφές του πρώτου μέρους του Kn,n προηγούνται των
κορυφών του δεύτερου του μέρους. Πέραν αυτών των αποτελεσμάτων, τα οποία
είναι θεωρητικής φύσης, αναπτύξαμε και μία διατύπωση SAT για το πρόβλημα
του ελέγχου εάν ένα δοθέν γράφημα επιδέχεται μιας γραμμικής απεικόνισης με
διπλοτόξα σε συγκεκριμένο αριθμό σελίδων. Τέλος, ενσωματώσαμε την υλοποίη-
σή μας σε ένα υπάρχον client-server λογισμικό, το οποίο υποστηρίζει διάφορους
τύπους γραμμικών απεικονίσεων, συμπεριλαμβανομένων και αυτών της στοίβας
και της ουράς.
Abstract In this thesis, we introduce and study on a new variant of linear layouts in which the vertices are arranged along a straight line, commonly referred to as spine, and the edges are partitioned into a certain number of parts, called pages, such that: (i) each page is a distinct plane containing the spine, (ii) each edge is drawn either as a half-circle above the spine or as a half-circle below the spine, or as two half-circles on opposite sides of the spine with a single common point located on the spine and inbetween the two endvertices of the edge, and (iii) no two edges of the same page cross. We refer to such linear layouts as monotone with biarcs. Given a graph, our interest is on its biarc number, that is, the minimum number of pages that are required for a linear layout with monotone biarcs to exist. Our contribution is as follows: We prove that the biarc number of Kn is at most ⌈ n 4 ⌉. This result is obtained via a general construction (of independent interest) which yields different linear layouts with monotone biarcs, in which the number of edges drawn as biarcs can be adjusted from 0 to n2 8 − n 4 + 2. We further show that the biarc number of Kn,n is at most ⌈ n 3 ⌉ + 1 in the separated setting, namely, when all vertices of one part of Kn,n precede those of its second part. Besides these results, which are of theoretical nature, we also developed a SAT formulation for the problem of testing whether a given graph admits a linear layout with biarcs on a certain number of pages. We integrated our implementation into an existing client-server tool, which supports various types of linear layouts, including the well-known stack and queue layouts.
Abstract In this thesis, we introduce and study on a new variant of linear layouts in which the vertices are arranged along a straight line, commonly referred to as spine, and the edges are partitioned into a certain number of parts, called pages, such that: (i) each page is a distinct plane containing the spine, (ii) each edge is drawn either as a half-circle above the spine or as a half-circle below the spine, or as two half-circles on opposite sides of the spine with a single common point located on the spine and inbetween the two endvertices of the edge, and (iii) no two edges of the same page cross. We refer to such linear layouts as monotone with biarcs. Given a graph, our interest is on its biarc number, that is, the minimum number of pages that are required for a linear layout with monotone biarcs to exist. Our contribution is as follows: We prove that the biarc number of Kn is at most ⌈ n 4 ⌉. This result is obtained via a general construction (of independent interest) which yields different linear layouts with monotone biarcs, in which the number of edges drawn as biarcs can be adjusted from 0 to n2 8 − n 4 + 2. We further show that the biarc number of Kn,n is at most ⌈ n 3 ⌉ + 1 in the separated setting, namely, when all vertices of one part of Kn,n precede those of its second part. Besides these results, which are of theoretical nature, we also developed a SAT formulation for the problem of testing whether a given graph admits a linear layout with biarcs on a certain number of pages. We integrated our implementation into an existing client-server tool, which supports various types of linear layouts, including the well-known stack and queue layouts.
Περιγραφή
Λέξεις-κλειδιά
Θεωρία γραφημάτων, Γραμμικές απεικονίσεις γραφημάτων, Διπλοτόξα, Μονότονα διπλοτόξα, Graph theory, Linear graph layouts, Biarcs, Monotone biarcs
Θεματική κατηγορία
Θεωρία Γραφημάτων, Graph Theory
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Bekos, Michael A.
Εξεταστική επιτροπή
Papadopoulos, Charis
Παπαδόπουλος, Χάρης
Georgiadis, Loukas
Γεωργιάδης, Λουκάς
Παπαδόπουλος, Χάρης
Georgiadis, Loukas
Γεωργιάδης, Λουκάς
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Ονόματα συντελεστών
Αριθμός σελίδων
46
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NoDerivs 3.0 United States