55 citations · 124 across the 16 of their papers we have counts for
19 papers
Unique Triangulated 1-Planar Graphs
Franz J. Brandenburg
It is well-known that every 3-connected planar graph has a unique planar embedding on the sphere. We study the extension to triangulated 1-planar graphs, T1P graphs for short, whic…
Embedding 1-Planar Graphs in Ten Pages
Franz J. Brandenburg
Every planar graph has a 4-page book embedding and this bound is tight. We show that every 1-planar graph, which is a graph that admits a drawing with at most one crossing per edge…
On Optimal Beyond-Planar Graphs
Franz J. Brandenburg
A graph is beyond-planar if it can be drawn in the plane with a specific restriction on crossings. Several types of beyond-planar graphs have been investigated, such as k-planar if…
Straight-line Drawings of 1-Planar Graphs
Franz J. Brandenburg
A graph is 1-planar if it can be drawn in the plane so that each edge is crossed at most once. However, there are 1-planar graphs which do not admit a straight-line 1-planar drawin…
Book Embeddings of k-Map Graphs
Franz J. Brandenburg
A map is a partition of the sphere into regions that are labeled as countries or holes. The vertices of a map graph are the countries of a map. There is an edge if and only if the…
Fan-Crossing Free Graphs and Their Relationship to other Beyond-Planar Graphs
Franz J. Brandenburg
A graph is \emph{fan-crossing free} if it has a drawing in the plane so that each edge is crossed by independent edges, that is the crossing edges have distinct vertices. On the ot…
Simple -Planar Graphs are Simple -Quasiplanar
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg +8
A simple topological graph is -quasiplanar () if it contains no pairwise crossing edges, and -planar if no edge is crossed more than times. In this paper, we…
On Fan-Crossing Graphs
Franz J. Brandenburg
A fan is a set of edges with a single common endpoint. A graph is fan-crossing if it admits a drawing in the plane so that each edge is crossed by edges of a fan. It is fan-planar…
A Note on IC-Planar Graphs
Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer
A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. IC-planarity speci…
T-Shape Visibility Representations of 1-Planar Graphs
Franz J. Brandenburg
A shape visibility representation displays a graph so that each vertex is represented by an orthogonal polygon of a particular shape and for each edge there is a horizontal or vert…
On the Relationship between -Planar and -Quasi Planar Graphs
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg +6
A graph is -planar if it can be drawn in the plane such that no edge is crossed more than times. A graph is -quasi planar if it can be drawn in…
Recognizing IC-Planar and NIC-Planar Graphs
Franz J. Brandenburg
We prove that triangulated IC-planar and NIC-planar graphs can be recognized in cubic time. A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge.…
Path-Additions of Graphs
Franz J. Brandenburg, Alexander Esch, Daniel Neuwirth
Path-addition is an operation that takes a graph and adds an internally vertex-disjoint path between two vertices together with a set of supplementary edges. Path-additions are jus…
Recognizing Optimal 1-Planar Graphs in Linear Time
Franz J. Brandenburg
A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of 4n-8 edges. We show that op…
A Reduction System for Optimal 1-Planar Graphs
Franz J. Brandenburg
There is a graph reduction system so that every optimal 1-planar graph can be reduced to an irreducible extended wheel graph, provided the reductions are applied such that the give…
On the Book Thickness of 1-Planar Graphs
Md. Jawaherul Alam, Franz J. Brandenburg, Stephen G. Kobourov
In a book embedding of a graph G, the vertices of G are placed in order along a straight-line called spine of the book, and the edges of G are drawn on a set of half-planes, called…
On 4-Map Graphs and 1-Planar Graphs and their Recognition Problem
Franz J. Brandenburg
We establish a one-to-one correspondence between 1-planar graphs and general and hole-free 4-map graphs and show that 1-planar graphs can be recognized in polynomial time if they a…
Recognizing and Drawing IC-planar Graphs
Franz J. Brandenburg, Walter Didimo, William S. Evans +3
IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-pl…
The Open Graph Archive: A Community-Driven Effort
Christian Bachmaier, Franz J. Brandenburg, Philip Effinger +6
In order to evaluate, compare, and tune graph algorithms, experiments on well designed benchmark sets have to be performed. Together with the goal of reproducibility of experimenta…