dc.contributor.author
Dangelmayr, Cornelia
dc.date.accessioned
2018-06-07T21:42:22Z
dc.date.available
2010-02-23T11:13:57.463Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/8303
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-12502
dc.description.abstract
In der vorliegenden Arbeit werden graphentheoretische Eigenschaften von
Durchschnittsgraphen von Pseudosegmenten, auch Pseudosegmentgraphen genannt,
bestimmt. Dabei verstehen wir unter einer Menge von Pseudosegmenten eine
endliche Menge von Jordankurven in der Euklidischen Ebene, für die gilt, dass
sich je zwei Kurven in höchstens einem Punkt treffen, der entweder ein
Kreuzungspunkt oder ein Endpunkt einer Kurve ist. Pseudosegmentgraphen gehören
zur Klasse der Kurvengraphen, die 1966 von Sinden eingeführt wurden. Bekannte
Beispiele von Kurvengraphen sind chordale und planare Graphen,
Unvergleichbarkeitsgraphen und Segmentgraphen. Im Jahre 1984 stellte
Scheinerman die Vermutung auf, dass jeder planare Graph ein Segmentgraph ist.
Diese Vermutung erregte das Interesse vieler Forscher, konnte aber erst im
Jahr 2009 bestätigt werden. Eine weitergehende Vermutung von West aus dem
Jahre 1991 besagt, dass jeder planare Graph eine Segmentdarstellung besizt, in
der die Segmente in höchstens vier Richtungen liegen. Dies ist weiterhin
offen. Diese Vermutungen veranlassten uns, Teilklassen von planaren Graphen,
insbesondere serien-parallele Graphen, zu betrachten. Unser Ergebnis zeigt,
dass jeder serien-parallele Graph eine Segmentdarstellung besitzt, in der die
Segmente in höchstens drei Richtungen liegen. Zur Unterscheidung von
Pseudosegment- und Segmentdarstellungen betrachten wir streckbare und
nichtstreckbare Arrangements von Pseudogeraden. Darauf aufbauend leiten wir
eine Konstruktion her, die Pseudosegmentgraphen erzeugt, die keine
Segmentgraphen sind. Im Anschluss beschäftigen wir uns mit der Beziehung von
chordalen und Pseudosegmentgraphen. Zum einen zeigen wir, dass Pfadgraphen
Pseudosegmentgraphen sind. Und zum anderen stellen wir chordale Graphen vor,
die keine Pseudosegmentgraphen sind; diese lassen sich zudem zur Beschränkung
der gemeinsame Teilklasse von chordalen und Pseudosegmentgraphen verwenden. Im
letzten Teil der Arbeit werden wir Trapezgraphen, eine Teilklasse von
Unvergleichbarkeitsgraphen, betrachten und Pseudosegmentdarstellungen von
Intervalgraphen, Punkt-Interval-Graphen und zwei weiteren Typen von
Trapezgraphen konstruieren.
de
dc.description.abstract
In this thesis we investigate graph-theoretic properties of intersection
graphs of pseudosegments. In this context, a set of pseudosegments is a set of
Jordan curves in the Euclidean plane, where any two curves have at most one
points of intersection where they cross. Pseudosegment graphs form a subclass
of the class of string graphs which were introduced in 1966 by Sinden.
Examples of string graphs are chordal graphs, planar graphs, cocomparability
graphs and segment graphs. In 1984, Scheinerman conjectured that every planar
graph was a segment graph. This conjecture initiated a lot of research and was
confirmed in 2009 by Chalopin and Goncalves. This conjecture was strengthened
by a conjecture of West, that every planar graph has a segment graph
consisting of segments of at most four directions. These conjectures motivated
us to consider subclasses of planar graphs. We show that every series-parallel
graph has a segment representation with segments of at most three directions.
To illustrate the difference between pseudosegment and segment graphs we
consider pseudoline arrangements. This results in a construction that yields
pseudosegment graphs that are not segment graphs. We then consider chordal
graphs in view of pseudosegment representations, and show that every path
graph is a pseudosegment graph. In the latter we define two families of
chordal graphs that are not pseudosegment graphs. In the latter we determine
cocomparability graphs that are pseudosegment graphs. Among these are interval
graphs, point-interval graphs and two further subclasses of trapezoid graphs.
en
dc.format.extent
IV, 136 S.
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
Intersection Graphs
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik
dc.title
Intersection graphs of pseudosegments
dc.contributor.firstReferee
Prof. Dr. Martin Aigner
dc.contributor.furtherReferee
Prof. Dr. Stefan Felsner
dc.date.accepted
2010-01-15
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000015370-3
dc.title.translated
Durchschnittsgraphen von Pseudosegmenten
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000015370
refubium.mycore.derivateId
FUDISS_derivate_000000006907
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access