Upward and quasi-upward planarity testing of embedded mixed graphs

作者：Binucci Carla; Didimo Walter^*; Patrignani Maurizio

来源：Theoretical Computer Science, 2014, 526: 75-89.

DOI：10.1016/j.tcs.2014.01.015

• Graph drawing
• Mixed graphs
• Upward planarity
• Quasi-upward planarity

Mixed graphs have both directed and undirected edges and have received considerable attention in the literature. We study two upward planarity testing problems for embedded mixed graphs, give some NP-hardness results, and describe Integer Linear Programming techniques to solve them. Experiments show the efficiency of our approach.

• 出版日期2014-3-20
• 单位Perugia