55 citations · 124 across the 16 of their papers we have counts for
4 papers · 1 filter
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…