National Technical University of Athens (NTUA)
Χρωματισμοί, εμφυτεύσεις και συναφή γραφοθεωρητικά προβλήματα
Abstract
dc:descriptionBook embeddings are a well studied topic of graph theory with numerous applications. Research dates back to early 70s and has produced a vast litterature. In this thesis we focus on two particular problems. The first was posed by Heath: he proved that planar graphs of maximum degree 3 are subhamiltonian and therofore 2-page book embeddable, and asked if the same holds for planar graphs of maximum degree greater than 3. In this concept we prove that all planar graphs of maximum degree 4 are indeed subhamiltonian. The second question is releted to the page number of graphs that are not closed under minors. It is well known that if a graph is closed under minors then its page number is bounded. However it remained open whether any bound exists for families of graphs that are not minor-closed. We prove that the class of 1-planar graphs, i.e. graphs that can be embedded in the plane so that every edge is crossed at most once, have bounded page number. To the best of our knowledge, this is the first attempt to bound the page number of such families of graphs. Another topic of graph theory that we focus on, are a variation of the well known total coloring problem. We consider total colorings that distinguish adjacent vertices by the sets of colors used for the vertex and its incident edges. This problem was proposed by Professor B\'ela Bollob\'as. In fact he suggested to consider AVD-total colorings of graphs with maximum degree 3, in order to answer a question posed by Hulgan of whether 5 colors suffice for such a coloring or 6 colors are necessary for certain 3-regular graphs. Although we did not manage to completely answer this question, we proved that 5 colors are enough for generalized Halin graphs with maximum degree 3. This is also a step towards determining the exact AVD-total coloring number of planar graphs. From another perspective, we also prove that the AVD-total coloring conjecture holds for 4-regular graphs. In this thesis, we also examine some problems of graph drawing. In particular, we answer an open question posed by Lov\'asz about circle representations of 4-regular planar graphs. Circle representations are related to the well known contact graph representation problem. We prove that if the graph is triconnected then circle-packing techniques can produce a realization as a system of touching circles, however if the graph is not triconnected then there exist infinite counterexamples. Also, we give new results on perfect smooth orthogonal layouts, that were recently introduced in the graph drawing litterature, and we extend and improve previous work on this topic.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Raftopoulou, Chrysanthi
- Ραυτοπούλου, Χρυσάνθη
Subjects
dc:subject × 8Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/43369