Journal: Journal of Graph Algorithms and Applications

Abbreviation

J. Graph Algorithms Appl.

Publisher

Brown University

Journal Volumes

ISSN

1526-1719

Description

Filters

2015 - 201912020 - 20232
Reset filters

Search Results

Publications 1 - 3 of 3
  • Drawing Shortest Paths in Geodetic Graphs
    Item type: Journal Article
    Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; et al. (2022)
    Journal of Graph Algorithms and Applications
    Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low.
  • Simplifying Non-Simple Fan-Planar Drawings
    Item type: Journal Article
    Klemz, Boris; Knorr, Kristin; Reddy, Meghana M.; et al. (2023)
    Journal of Graph Algorithms and Applications
    A drawing of a graph is fan-planar if the edges intersecting a common edge a share a vertex A on the same side of a. More precisely, orienting a arbitrarily and the other edges towards A results in a consistent orientation of the crossings. So far, fan-planar drawings have only been considered in the context of simple drawings, where any two edges share at most one point, including endpoints. We show that every non-simple fan-planar drawing can be redrawn as a simple fan-planar drawing of the same graph while not introducing additional crossings. The proof is constructive and corresponds to a quadratic time algorithm. Combined with previous results on fan-planar drawings, this yields that n-vertex graphs having such a drawing can have at most 6.5n - 20 edges and that the recognition of such graphs is NP-hard. We thereby answer an open problem posed by Kaufmann and Ueckerdt in 2014.
  • On universal point sets for planar graphs
    Item type: Journal Article
    Cardinal, Jean; Hoffmann, Michael; Kusters, Vincent (2015)
    Journal of Graph Algorithms and Applications
Publications 1 - 3 of 3