[Back]

F. Klute, M. Nöllenburg:
"Minimizing crossings in constrained two-sided circular graph layouts";
Talk: EuroCG17, Schweden (invited); 2017-05-05.

Circular layouts are a popular graph drawing style,
where vertices are placed on a circle and edges are
drawn as straight chords. One way to reduce clutter
caused by edge crossings is to use
two-sided circular
layouts
, in which some edges are drawn as curves in
the exterior of the circle. We study the problem of
minimizing the crossings for a
fi
xed cyclic vertex or-
der by computing an optimal 1-plane set of exteriorly
drawn edges. This relates to
fi
nding maximum-weight
degree-constrained induced subgraphs in circle or over-
lap graphs.