Drawing Bipartite Graphs in Two Layers with Specified Crossings

• Autoři: DIWAN Ajit Arvind; ROY Bodhayan; GHOSH Subir Kumar
• Rok publikování: 2019
• Druh: Článek ve sborníku
• Konference: 5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019)
• Fakulta / Pracoviště MU: Fakulta informatiky
• Doi: https://doi.org/10.1007/978-3-030-11509-8_9
• Klíčová slova: Abstract topological graph; Bipartite graph; Permutation graph; Two-layer drawing
• Popis: We give a polynomial-time algorithm to decide whether a bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of edges cross. This is a generalization of the problem of recognizing permutation graphs, and we generalize the characterization of permutation graphs.

Související projekty

• Structural properties, parameterized tractability and hardness in combinatorial problems