Splitting Vertices in 2-Layer Graph Drawings Article Swipe
Reyan Ahmed
,
Patrizio Angelini
,
Michael A. Bekos
,
Giuseppe Di Battista
,
Michael Kaufmann
,
Philipp Kindermann
,
Stephen Kobourov
,
Martin Nöllenburg
,
Antonios Symvonis
,
Anaïs Villedieu
,
Markus Wallinger
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2301.10872
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2301.10872
Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the number of edge crossings. We use vertex splitting to reduce the number of crossings, by replacing selected vertices on one layer by two (or more) copies and suitably distributing their incident edges among these copies. We study several optimization problems related to vertex splitting, either minimizing the number of crossings or removing all crossings with fewest splits. While we prove that some variants are \NP-complete, we obtain polynomial-time algorithms for others. We run our algorithms on a benchmark set of bipartite graphs representing the relationships between human anatomical structures and cell types.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2301.10872
- https://arxiv.org/pdf/2301.10872
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4318348225
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4318348225Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2301.10872Digital Object Identifier
- Title
-
Splitting Vertices in 2-Layer Graph DrawingsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-01-25Full publication date if available
- Authors
-
Reyan Ahmed, Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Michael Kaufmann, Philipp Kindermann, Stephen Kobourov, Martin Nöllenburg, Antonios Symvonis, Anaïs Villedieu, Markus WallingerList of authors in order
- Landing page
-
https://arxiv.org/abs/2301.10872Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2301.10872Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2301.10872Direct OA link when available
- Concepts
-
Bipartite graph, Combinatorics, Vertex (graph theory), Disjoint sets, Computer science, Enhanced Data Rates for GSM Evolution, Graph, Mathematics, Artificial intelligenceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4318348225 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2301.10872 |
| ids.doi | https://doi.org/10.48550/arxiv.2301.10872 |
| ids.openalex | https://openalex.org/W4318348225 |
| fwci | |
| type | preprint |
| title | Splitting Vertices in 2-Layer Graph Drawings |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10222 |
| topics[0].field.id | https://openalex.org/fields/13 |
| topics[0].field.display_name | Biochemistry, Genetics and Molecular Biology |
| topics[0].score | 0.9965000152587891 |
| topics[0].domain.id | https://openalex.org/domains/1 |
| topics[0].domain.display_name | Life Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1312 |
| topics[0].subfield.display_name | Molecular Biology |
| topics[0].display_name | Genomics and Chromatin Dynamics |
| topics[1].id | https://openalex.org/T10996 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9952999949455261 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1704 |
| topics[1].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[1].display_name | Computational Geometry and Mesh Generation |
| topics[2].id | https://openalex.org/T12923 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9866999983787537 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1707 |
| topics[2].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[2].display_name | Digital Image Processing Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C197657726 |
| concepts[0].level | 3 |
| concepts[0].score | 0.7718324065208435 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q174733 |
| concepts[0].display_name | Bipartite graph |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6975002288818359 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C80899671 |
| concepts[2].level | 3 |
| concepts[2].score | 0.6145453453063965 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[2].display_name | Vertex (graph theory) |
| concepts[3].id | https://openalex.org/C45340560 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5172653794288635 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q215382 |
| concepts[3].display_name | Disjoint sets |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.4791938066482544 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C162307627 |
| concepts[5].level | 2 |
| concepts[5].score | 0.43074238300323486 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q204833 |
| concepts[5].display_name | Enhanced Data Rates for GSM Evolution |
| concepts[6].id | https://openalex.org/C132525143 |
| concepts[6].level | 2 |
| concepts[6].score | 0.39597421884536743 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[6].display_name | Graph |
| concepts[7].id | https://openalex.org/C33923547 |
| concepts[7].level | 0 |
| concepts[7].score | 0.3754497170448303 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[7].display_name | Mathematics |
| concepts[8].id | https://openalex.org/C154945302 |
| concepts[8].level | 1 |
| concepts[8].score | 0.08433488011360168 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[8].display_name | Artificial intelligence |
| keywords[0].id | https://openalex.org/keywords/bipartite-graph |
| keywords[0].score | 0.7718324065208435 |
| keywords[0].display_name | Bipartite graph |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.6975002288818359 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/vertex |
| keywords[2].score | 0.6145453453063965 |
| keywords[2].display_name | Vertex (graph theory) |
| keywords[3].id | https://openalex.org/keywords/disjoint-sets |
| keywords[3].score | 0.5172653794288635 |
| keywords[3].display_name | Disjoint sets |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.4791938066482544 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/enhanced-data-rates-for-gsm-evolution |
| keywords[5].score | 0.43074238300323486 |
| keywords[5].display_name | Enhanced Data Rates for GSM Evolution |
| keywords[6].id | https://openalex.org/keywords/graph |
| keywords[6].score | 0.39597421884536743 |
| keywords[6].display_name | Graph |
| keywords[7].id | https://openalex.org/keywords/mathematics |
| keywords[7].score | 0.3754497170448303 |
| keywords[7].display_name | Mathematics |
| keywords[8].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[8].score | 0.08433488011360168 |
| keywords[8].display_name | Artificial intelligence |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2301.10872 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://arxiv.org/pdf/2301.10872 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2301.10872 |
| locations[1].id | doi:10.48550/arxiv.2301.10872 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2301.10872 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5001115259 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-6830-9053 |
| authorships[0].author.display_name | Reyan Ahmed |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ahmed, Reyan |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5010111302 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-7602-1524 |
| authorships[1].author.display_name | Patrizio Angelini |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Angelini, Patrizio |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5006472576 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-3414-7444 |
| authorships[2].author.display_name | Michael A. Bekos |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Bekos, Michael A. |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5038655759 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-4224-1550 |
| authorships[3].author.display_name | Giuseppe Di Battista |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Di Battista, Giuseppe |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5103045561 |
| authorships[4].author.orcid | https://orcid.org/0000-0001-9186-3538 |
| authorships[4].author.display_name | Michael Kaufmann |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Kaufmann, Michael |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5029516206 |
| authorships[5].author.orcid | https://orcid.org/0000-0001-5764-7719 |
| authorships[5].author.display_name | Philipp Kindermann |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Kindermann, Philipp |
| authorships[5].is_corresponding | False |
| authorships[6].author.id | https://openalex.org/A5003147292 |
| authorships[6].author.orcid | https://orcid.org/0000-0002-0477-2724 |
| authorships[6].author.display_name | Stephen Kobourov |
| authorships[6].author_position | middle |
| authorships[6].raw_author_name | Kobourov, Stephen |
| authorships[6].is_corresponding | False |
| authorships[7].author.id | https://openalex.org/A5071390048 |
| authorships[7].author.orcid | https://orcid.org/0000-0003-0454-3937 |
| authorships[7].author.display_name | Martin Nöllenburg |
| authorships[7].author_position | middle |
| authorships[7].raw_author_name | Nöllenburg, Martin |
| authorships[7].is_corresponding | False |
| authorships[8].author.id | https://openalex.org/A5011976306 |
| authorships[8].author.orcid | https://orcid.org/0000-0002-0280-741X |
| authorships[8].author.display_name | Antonios Symvonis |
| authorships[8].author_position | middle |
| authorships[8].raw_author_name | Symvonis, Antonios |
| authorships[8].is_corresponding | False |
| authorships[9].author.id | https://openalex.org/A5079181794 |
| authorships[9].author.orcid | https://orcid.org/0000-0001-6196-8347 |
| authorships[9].author.display_name | Anaïs Villedieu |
| authorships[9].author_position | middle |
| authorships[9].raw_author_name | Villedieu, Anaïs |
| authorships[9].is_corresponding | False |
| authorships[10].author.id | https://openalex.org/A5034814164 |
| authorships[10].author.orcid | https://orcid.org/0000-0002-2191-4413 |
| authorships[10].author.display_name | Markus Wallinger |
| authorships[10].author_position | last |
| authorships[10].raw_author_name | Wallinger, Markus |
| authorships[10].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2301.10872 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Splitting Vertices in 2-Layer Graph Drawings |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10222 |
| primary_topic.field.id | https://openalex.org/fields/13 |
| primary_topic.field.display_name | Biochemistry, Genetics and Molecular Biology |
| primary_topic.score | 0.9965000152587891 |
| primary_topic.domain.id | https://openalex.org/domains/1 |
| primary_topic.domain.display_name | Life Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1312 |
| primary_topic.subfield.display_name | Molecular Biology |
| primary_topic.display_name | Genomics and Chromatin Dynamics |
| related_works | https://openalex.org/W2371352078, https://openalex.org/W2953461625, https://openalex.org/W4256429076, https://openalex.org/W1971174658, https://openalex.org/W2077383796, https://openalex.org/W2080136900, https://openalex.org/W2099195351, https://openalex.org/W2999799752, https://openalex.org/W2372768926, https://openalex.org/W2115167491 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2301.10872 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2301.10872 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2301.10872 |
| primary_location.id | pmh:oai:arXiv.org:2301.10872 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://arxiv.org/pdf/2301.10872 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2301.10872 |
| publication_date | 2023-01-25 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 134 |
| abstract_inverted_index.In | 22 |
| abstract_inverted_index.We | 62, 93, 129 |
| abstract_inverted_index.as | 18 |
| abstract_inverted_index.by | 44, 72, 79 |
| abstract_inverted_index.in | 11 |
| abstract_inverted_index.of | 9, 28, 59, 70, 106, 137 |
| abstract_inverted_index.on | 33, 76, 133 |
| abstract_inverted_index.or | 108 |
| abstract_inverted_index.to | 55, 66, 99 |
| abstract_inverted_index.we | 116, 123 |
| abstract_inverted_index.(or | 81 |
| abstract_inverted_index.all | 110 |
| abstract_inverted_index.and | 14, 38, 84, 147 |
| abstract_inverted_index.are | 15, 31, 42, 121 |
| abstract_inverted_index.for | 49, 127 |
| abstract_inverted_index.one | 77 |
| abstract_inverted_index.our | 131 |
| abstract_inverted_index.run | 130 |
| abstract_inverted_index.set | 136 |
| abstract_inverted_index.the | 3, 25, 57, 68, 104, 141 |
| abstract_inverted_index.try | 54 |
| abstract_inverted_index.two | 6, 26, 34, 80 |
| abstract_inverted_index.use | 63 |
| abstract_inverted_index.cell | 148 |
| abstract_inverted_index.edge | 60 |
| abstract_inverted_index.sets | 8, 27 |
| abstract_inverted_index.some | 119 |
| abstract_inverted_index.such | 23 |
| abstract_inverted_index.that | 118 |
| abstract_inverted_index.with | 112 |
| abstract_inverted_index.While | 115 |
| abstract_inverted_index.among | 90 |
| abstract_inverted_index.drawn | 17 |
| abstract_inverted_index.edges | 89 |
| abstract_inverted_index.graph | 20 |
| abstract_inverted_index.human | 144 |
| abstract_inverted_index.layer | 78 |
| abstract_inverted_index.lines | 36 |
| abstract_inverted_index.model | 2 |
| abstract_inverted_index.more) | 82 |
| abstract_inverted_index.often | 53 |
| abstract_inverted_index.prove | 117 |
| abstract_inverted_index.study | 94 |
| abstract_inverted_index.their | 39, 87 |
| abstract_inverted_index.these | 91 |
| abstract_inverted_index.copies | 83 |
| abstract_inverted_index.either | 102 |
| abstract_inverted_index.fewest | 113 |
| abstract_inverted_index.graphs | 1, 139 |
| abstract_inverted_index.number | 58, 69, 105 |
| abstract_inverted_index.obtain | 124 |
| abstract_inverted_index.placed | 32 |
| abstract_inverted_index.reduce | 67 |
| abstract_inverted_index.types. | 149 |
| abstract_inverted_index.vertex | 64, 100 |
| abstract_inverted_index.(edges) | 41 |
| abstract_inverted_index.2-layer | 19, 51 |
| abstract_inverted_index.Methods | 48 |
| abstract_inverted_index.between | 5, 143 |
| abstract_inverted_index.copies. | 92 |
| abstract_inverted_index.others. | 128 |
| abstract_inverted_index.related | 98 |
| abstract_inverted_index.several | 12, 95 |
| abstract_inverted_index.splits. | 114 |
| abstract_inverted_index.disjoint | 7 |
| abstract_inverted_index.drawings | 52 |
| abstract_inverted_index.entities | 10, 29 |
| abstract_inverted_index.incident | 88 |
| abstract_inverted_index.minimize | 56 |
| abstract_inverted_index.parallel | 35 |
| abstract_inverted_index.problems | 97 |
| abstract_inverted_index.removing | 109 |
| abstract_inverted_index.segments | 45 |
| abstract_inverted_index.selected | 74 |
| abstract_inverted_index.suitably | 85 |
| abstract_inverted_index.variants | 120 |
| abstract_inverted_index.vertices | 75 |
| abstract_inverted_index.(layers), | 37 |
| abstract_inverted_index.Bipartite | 0 |
| abstract_inverted_index.benchmark | 135 |
| abstract_inverted_index.bipartite | 138 |
| abstract_inverted_index.crossings | 107, 111 |
| abstract_inverted_index.drawings, | 24 |
| abstract_inverted_index.drawings. | 21 |
| abstract_inverted_index.naturally | 16 |
| abstract_inverted_index.replacing | 73 |
| abstract_inverted_index.splitting | 65 |
| abstract_inverted_index.vertices. | 47 |
| abstract_inverted_index.(vertices) | 30 |
| abstract_inverted_index.algorithms | 126, 132 |
| abstract_inverted_index.anatomical | 145 |
| abstract_inverted_index.connecting | 46 |
| abstract_inverted_index.crossings, | 71 |
| abstract_inverted_index.crossings. | 61 |
| abstract_inverted_index.minimizing | 103 |
| abstract_inverted_index.splitting, | 101 |
| abstract_inverted_index.structures | 146 |
| abstract_inverted_index.represented | 43 |
| abstract_inverted_index.applications | 13 |
| abstract_inverted_index.constructing | 50 |
| abstract_inverted_index.distributing | 86 |
| abstract_inverted_index.optimization | 96 |
| abstract_inverted_index.representing | 140 |
| abstract_inverted_index.\NP-complete, | 122 |
| abstract_inverted_index.relationships | 4, 40, 142 |
| abstract_inverted_index.polynomial-time | 125 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 11 |
| citation_normalized_percentile |