Γραμμικές απεικονίσεις γραφημάτων με διπλοτόξα
| dc.contributor.author | Βελισσάρης, Γεώργιος | el |
| dc.contributor.author | Velissaris, Georgios | en |
| dc.date.accessioned | 2024-07-25T08:31:58Z | |
| dc.date.available | 2024-07-25T08:31:58Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/38245 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.17951 | |
| dc.rights | Attribution-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nd/3.0/us/ | * |
| dc.subject | Θεωρία γραφημάτων | el |
| dc.subject | Γραμμικές απεικονίσεις γραφημάτων | el |
| dc.subject | Διπλοτόξα | el |
| dc.subject | Μονότονα διπλοτόξα | el |
| dc.subject | Graph theory | en |
| dc.subject | Linear graph layouts | en |
| dc.subject | Biarcs | en |
| dc.subject | Monotone biarcs | en |
| dc.title | Γραμμικές απεικονίσεις γραφημάτων με διπλοτόξα | el |
| dc.title | Linear graph layouts with biarcs | en |
| dc.type | masterThesis | |
| heal.abstract | Στην παρούσα διατριβή εισάγουμε και μελετάμε μία νέα παραλλαγή γραμμικών απεικονίσεων γραφημάτων σύμφωνα με την οποία οι κορυφές του γραφήματος δια- τάσσονται κατά μήκος μιας ευθείας γραμμής, η οποία συχνά αναφέρεται ως ράχη, ενώ οι ακμές του γραφήματος διαμερίζονται σε σύνολα, τα οποία ονομάζονται σε- λίδες. Στην παραλλαγή που μελετάμε: (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 λογισμικό, το οποίο υποστηρίζει διάφορους τύπους γραμμικών απεικονίσεων, συμπεριλαμβανομένων και αυτών της στοίβας και της ουράς. | el |
| heal.abstract | 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. | en |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | el |
| heal.access | free | el |
| heal.advisorName | Bekos, Michael A. | en |
| heal.classification | Θεωρία Γραφημάτων | el |
| heal.classification | Graph Theory | en |
| heal.committeeMemberName | Papadopoulos, Charis | en |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Georgiadis, Loukas | en |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.dateAvailable | 2024-07-25T08:32:58Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | el |
| heal.numberOfPages | 46 | el |
| heal.publicationDate | 2024-07-09 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών | el |
| heal.type | masterThesis | el |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Linear Layouts With Biarcs - Georgios Velissaris.pdf
- Μέγεθος:
- 1.47 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 3.22 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: