Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Drawing Graphs with Vertices at specified Positions and Crossings at Large Angles

02/21/2012

Point set embeddings of graphs are drawings of graphs in which nodes lie only on positions allowed by a specified input point set. At chair I such embeddings have been investigated with the additional constraint that all crossing angles of two edges are large. Martin Fink presents the results at the conference WALCOM'12.

A well-known problem in graph drawing is point set embeddability. In this setting, one is given a set of allowed vertex positions, additionally to the graph. In a more restricted version even the exact positions of the vertices are fixed and the only freedom is the drawing of the edges, which can be done using, e.g., two or three bends. Until now, only variants of the problem with crossing-free drawings have been considered. In contrast to that, Martin Fink, Jan Haunert, Tamara Mchedlidze, Joachim Spoerhase and, Alexander Wolff investigated variants in which crossings of edges are allowed, but only at large crossing angles.

Point set embeddability restricted to crossing-free drawings has been investigated several times. It has already been known that the version of the problem with straight-line edges is NP-hard. As it turned out, this holds even when crossings are allowed, but only if the crossing angle is large. It also has been known that any planar graph can be embedded on any point set of adequate size when two bends per edge are allowed. If, however, the exact position of each vertex is specified, the number of necessary bends per edge cannot be bounded by a constant even for path graphs. In contrast to these previous results, any graph with fixed position of each vertex can be drawn with large crossing angles and at most one bend per edge. If three bends per edge are allowed, then the crossings can even be restricted to right angle crossings.

Details and additional results can be found in the conference article and the slides of the talk.

Back