Computing k-Modal Embeddings of Planar Digraphs

07/02/2019
by   Juan Jose Besa, et al.
0

Given a planar digraph G and a positive even integer k, an embedding of G in the plane is k-modal, if every vertex of G is incident to at most k pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. In this paper, we study the k-Modality problem, which asks for the existence of a k-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset