A Mixed-Integer Program for Drawing Orthogonal Hyperedges in a Hierarchical Hypergraph

Gregory Fridman, Yuri Vasiliev, Vlada Puhkalo and Vladimir Ryzhov
Additional contact information
Gregory Fridman: Department of Applied Mathematics and Mathematical Methods in Economics, Saint Petersburg State University of Economics, Griboedov Canal Emb., 30-32, 191023 St. Petersburg, Russia
Yuri Vasiliev: Department of Applied Mathematics and Mathematical Methods in Economics, Saint Petersburg State University of Economics, Griboedov Canal Emb., 30-32, 191023 St. Petersburg, Russia
Vlada Puhkalo: Department of Applied Mathematics and Mathematical Methods in Economics, Saint Petersburg State University of Economics, Griboedov Canal Emb., 30-32, 191023 St. Petersburg, Russia
Vladimir Ryzhov: Department of Applied Mathematics and Mathematical Modeling, Saint Petersburg State Marine Technical University, Lotsmanskaya Ulitsa, 3, 190121 St. Petersburg, Russia

Mathematics, 2022, vol. 10, issue 5, 1-15

Abstract: This paper presents a new formulation and solution of a mixed-integer program for the hierarchical orthogonal hypergraph drawing problem, and the number of hyperedge crossings is minimized. The novel feature of the model is in combining several stages of the Sugiyama framework for graph drawing: vertex ordering, the assignment of vertices’ x -coordinates, and orthogonal hyperedge routing. The hyperedges of a hypergraph are assumed to be multi-source and multi-target, and vertices are depicted as rectangles with ports on their top and bottom sides. Such hypergraphs are used in data-flow diagrams and in a scheme of cooperation. The numerical results demonstrate the correctness and effectiveness of the proposed approach compared to mathematical heuristics. For instance, the proposed exact approach yields a 67.3 % reduction of the number of crossings compared to that obtained by using a mathematical heuristic for a dataset of non-planar graphs.

Keywords: directed acyclic hierarchical graph; graph drawing; hypergraph; orthogonal hyperedge routing; branch-and-bound method; mathematical heuristic; financial flow (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/5/689/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/5/689/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:5:p:689-:d:756428

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().