Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2025)

<Previous Article In Volume
Next Article In Volume>

Crossing Minimization in k-layered Hierarchical Graphs: A Hybrid Approach

Authors
Loridge Anne Gacho1, Zandrew Peter Garais1, *, Nestine Hope Hernandez1, Jhoirene Clemente1
1Algorithms and Complexity Laboratory, University of the Philippines Diliman, Quezon City, Philippines
*Corresponding author. Email: zcgarais@alumni.up.edu.ph
Corresponding Author
Zandrew Peter Garais
Available Online 30 April 2026.
DOI
10.2991/978-94-6239-638-8_21How to use a DOI?
Keywords
computational geometry; graph theory; crossing minimization
Abstract

Minimizing edge crossings in graph drawings is crucial for improving readability. One variant, the k-layered hierarchical crossing minimization problem, seeks optimal vertex orderings across all layers of a k-layered graph to reduce crossings. We explore a hybrid layer-bylayer approach that combines two among the one-sided bipartite crossing minimization (OSCM) heuristics, barycenter, permutation, and sifting. These heuristics are applied above and below a specified cut-off index, dividing the graph into upper and lower regions. We implemented six hybrid cut-off algorithms and tested them on sparse k-layered graphs with ten (10) layers with layer widths b = 7 and b = 8, and edge counts defined by | E | = 2 · ( k - 1 ) · b . The results demonstrate trade-offs: heuristics with higher solution quality generally incur higher computational cost. For time-sensitive applications, faster hybrids like bary _ sift and sift _ bary are preferable, whereas permu _ sift and sift _ permu are more suitable when solution quality is prioritized. Selecting the appropriate hybrid and cut-off value is key to balancing performance and efficiency.

Copyright
© 2026 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2025)
Series
Atlantis Highlights in Computer Sciences
Publication Date
30 April 2026
ISBN
978-94-6239-638-8
ISSN
2589-4900
DOI
10.2991/978-94-6239-638-8_21How to use a DOI?
Copyright
© 2026 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Cite this article

risenwbib
TY  - CONF
AU  - Loridge Anne Gacho
AU  - Zandrew Peter Garais
AU  - Nestine Hope Hernandez
AU  - Jhoirene Clemente
PY  - 2026
DA  - 2026/04/30
TI  - Crossing Minimization in k-layered Hierarchical Graphs: A Hybrid Approach
BT  - Proceedings of the  Workshop on Computation: Theory and Practice (WCTP 2025)
PB  - Atlantis Press
SP  - 418
EP  - 444
SN  - 2589-4900
UR  - https://doi.org/10.2991/978-94-6239-638-8_21
DO  - 10.2991/978-94-6239-638-8_21
ID  - Gacho2026
ER  -