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.

Created from the Publication Database of the Vienna University of Technology.