An FPT Algorithm for Bipartite Vertex Splitting Article Swipe
Reyan Ahmed
,
Stephen Kobourov
,
Myroslav Kryven
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.12898
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.12898
Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as a 2-layered drawing, where each set of objects is visualized as a set of vertices (points) on one of the two parallel horizontal lines and the relationships are represented by edges (simple curves) between the two lines connecting the corresponding vertices. One of the common objectives in such drawings is to minimize the number of crossings this, however, is computationally expensive and may still result in drawings with so many crossings that they affect the readability of the drawing. We consider a recent approach to remove crossings in such visualizations by splitting vertices, where the goal is to find the minimum number of vertices to be split to obtain a planar drawing. We show that determining whether a planar drawing exists after splitting at most $k$ vertices is fixed parameter tractable in $k$.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2208.12898
- https://arxiv.org/pdf/2208.12898
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4293790982
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4293790982Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2208.12898Digital Object Identifier
- Title
-
An FPT Algorithm for Bipartite Vertex SplittingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-08-27Full publication date if available
- Authors
-
Reyan Ahmed, Stephen Kobourov, Myroslav KryvenList of authors in order
- Landing page
-
https://arxiv.org/abs/2208.12898Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2208.12898Direct 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/2208.12898Direct OA link when available
- Concepts
-
Bipartite graph, Vertex (graph theory), Disjoint sets, Combinatorics, Graph drawing, Planar, Set (abstract data type), Readability, Planar graph, Mathematics, Computer science, Algorithm, Graph, Computer graphics (images), Programming languageTop 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/W4293790982 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2208.12898 |
| ids.doi | https://doi.org/10.48550/arxiv.2208.12898 |
| ids.openalex | https://openalex.org/W4293790982 |
| fwci | |
| type | preprint |
| title | An FPT Algorithm for Bipartite Vertex Splitting |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10996 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.996999979019165 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1704 |
| topics[0].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[0].display_name | Computational Geometry and Mesh Generation |
| topics[1].id | https://openalex.org/T10374 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9301000237464905 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Advanced Graph Theory Research |
| topics[2].id | https://openalex.org/T12176 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9169999957084656 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2209 |
| topics[2].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[2].display_name | Optimization and Packing Problems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C197657726 |
| concepts[0].level | 3 |
| concepts[0].score | 0.8289999961853027 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q174733 |
| concepts[0].display_name | Bipartite graph |
| concepts[1].id | https://openalex.org/C80899671 |
| concepts[1].level | 3 |
| concepts[1].score | 0.7001863718032837 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[1].display_name | Vertex (graph theory) |
| concepts[2].id | https://openalex.org/C45340560 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6791514754295349 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q215382 |
| concepts[2].display_name | Disjoint sets |
| concepts[3].id | https://openalex.org/C114614502 |
| concepts[3].level | 1 |
| concepts[3].score | 0.5951667428016663 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[3].display_name | Combinatorics |
| concepts[4].id | https://openalex.org/C112953755 |
| concepts[4].level | 3 |
| concepts[4].score | 0.5818307995796204 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q739462 |
| concepts[4].display_name | Graph drawing |
| concepts[5].id | https://openalex.org/C134786449 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5233889222145081 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3391255 |
| concepts[5].display_name | Planar |
| concepts[6].id | https://openalex.org/C177264268 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4878940284252167 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[6].display_name | Set (abstract data type) |
| concepts[7].id | https://openalex.org/C2778143727 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4440114498138428 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1820650 |
| concepts[7].display_name | Readability |
| concepts[8].id | https://openalex.org/C101837359 |
| concepts[8].level | 3 |
| concepts[8].score | 0.4332003593444824 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q547823 |
| concepts[8].display_name | Planar graph |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.4321076273918152 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C41008148 |
| concepts[10].level | 0 |
| concepts[10].score | 0.39518797397613525 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[10].display_name | Computer science |
| concepts[11].id | https://openalex.org/C11413529 |
| concepts[11].level | 1 |
| concepts[11].score | 0.35218507051467896 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[11].display_name | Algorithm |
| concepts[12].id | https://openalex.org/C132525143 |
| concepts[12].level | 2 |
| concepts[12].score | 0.19481214880943298 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[12].display_name | Graph |
| concepts[13].id | https://openalex.org/C121684516 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0858672559261322 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7600677 |
| concepts[13].display_name | Computer graphics (images) |
| concepts[14].id | https://openalex.org/C199360897 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[14].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/bipartite-graph |
| keywords[0].score | 0.8289999961853027 |
| keywords[0].display_name | Bipartite graph |
| keywords[1].id | https://openalex.org/keywords/vertex |
| keywords[1].score | 0.7001863718032837 |
| keywords[1].display_name | Vertex (graph theory) |
| keywords[2].id | https://openalex.org/keywords/disjoint-sets |
| keywords[2].score | 0.6791514754295349 |
| keywords[2].display_name | Disjoint sets |
| keywords[3].id | https://openalex.org/keywords/combinatorics |
| keywords[3].score | 0.5951667428016663 |
| keywords[3].display_name | Combinatorics |
| keywords[4].id | https://openalex.org/keywords/graph-drawing |
| keywords[4].score | 0.5818307995796204 |
| keywords[4].display_name | Graph drawing |
| keywords[5].id | https://openalex.org/keywords/planar |
| keywords[5].score | 0.5233889222145081 |
| keywords[5].display_name | Planar |
| keywords[6].id | https://openalex.org/keywords/set |
| keywords[6].score | 0.4878940284252167 |
| keywords[6].display_name | Set (abstract data type) |
| keywords[7].id | https://openalex.org/keywords/readability |
| keywords[7].score | 0.4440114498138428 |
| keywords[7].display_name | Readability |
| keywords[8].id | https://openalex.org/keywords/planar-graph |
| keywords[8].score | 0.4332003593444824 |
| keywords[8].display_name | Planar graph |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.4321076273918152 |
| keywords[9].display_name | Mathematics |
| keywords[10].id | https://openalex.org/keywords/computer-science |
| keywords[10].score | 0.39518797397613525 |
| keywords[10].display_name | Computer science |
| keywords[11].id | https://openalex.org/keywords/algorithm |
| keywords[11].score | 0.35218507051467896 |
| keywords[11].display_name | Algorithm |
| keywords[12].id | https://openalex.org/keywords/graph |
| keywords[12].score | 0.19481214880943298 |
| keywords[12].display_name | Graph |
| keywords[13].id | https://openalex.org/keywords/computer-graphics |
| keywords[13].score | 0.0858672559261322 |
| keywords[13].display_name | Computer graphics (images) |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2208.12898 |
| 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 | |
| locations[0].pdf_url | https://arxiv.org/pdf/2208.12898 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2208.12898 |
| locations[1].id | doi:10.48550/arxiv.2208.12898 |
| 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.2208.12898 |
| 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/A5003147292 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-0477-2724 |
| authorships[1].author.display_name | Stephen Kobourov |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Kobourov, Stephen |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5045237218 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-4778-3703 |
| authorships[2].author.display_name | Myroslav Kryven |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Kryven, Myroslav |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2208.12898 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | An FPT Algorithm for Bipartite Vertex Splitting |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10996 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.996999979019165 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1704 |
| primary_topic.subfield.display_name | Computer Graphics and Computer-Aided Design |
| primary_topic.display_name | Computational Geometry and Mesh Generation |
| related_works | https://openalex.org/W2210665824, https://openalex.org/W2048639803, https://openalex.org/W2113444201, https://openalex.org/W4287272854, https://openalex.org/W2604486243, https://openalex.org/W2470646738, https://openalex.org/W130561602, https://openalex.org/W2337656972, https://openalex.org/W2953014750, https://openalex.org/W1628543033 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2208.12898 |
| 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 | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2208.12898 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| 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/2208.12898 |
| primary_location.id | pmh:oai:arXiv.org:2208.12898 |
| 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 | |
| primary_location.pdf_url | https://arxiv.org/pdf/2208.12898 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2208.12898 |
| publication_date | 2022-08-27 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 13, 23, 34, 104, 132, 140 |
| abstract_inverted_index.We | 102, 135 |
| abstract_inverted_index.as | 22, 33 |
| abstract_inverted_index.at | 146 |
| abstract_inverted_index.be | 128 |
| abstract_inverted_index.by | 52, 113 |
| abstract_inverted_index.in | 69, 88, 110, 154 |
| abstract_inverted_index.is | 31, 72, 81, 119, 150 |
| abstract_inverted_index.of | 9, 16, 29, 36, 41, 65, 77, 99, 125 |
| abstract_inverted_index.on | 39 |
| abstract_inverted_index.so | 91 |
| abstract_inverted_index.to | 73, 107, 120, 127, 130 |
| abstract_inverted_index.$k$ | 148 |
| abstract_inverted_index.One | 64 |
| abstract_inverted_index.and | 18, 47, 84 |
| abstract_inverted_index.are | 19, 50 |
| abstract_inverted_index.may | 85 |
| abstract_inverted_index.one | 40 |
| abstract_inverted_index.set | 28, 35 |
| abstract_inverted_index.the | 3, 42, 48, 57, 61, 66, 75, 97, 100, 117, 122 |
| abstract_inverted_index.two | 6, 43, 58 |
| abstract_inverted_index.$k$. | 155 |
| abstract_inverted_index.They | 11 |
| abstract_inverted_index.each | 27 |
| abstract_inverted_index.find | 121 |
| abstract_inverted_index.goal | 118 |
| abstract_inverted_index.have | 12 |
| abstract_inverted_index.many | 92 |
| abstract_inverted_index.most | 147 |
| abstract_inverted_index.sets | 8 |
| abstract_inverted_index.show | 136 |
| abstract_inverted_index.such | 70, 111 |
| abstract_inverted_index.that | 94, 137 |
| abstract_inverted_index.they | 95 |
| abstract_inverted_index.wide | 14 |
| abstract_inverted_index.with | 90 |
| abstract_inverted_index.after | 144 |
| abstract_inverted_index.edges | 53 |
| abstract_inverted_index.fixed | 151 |
| abstract_inverted_index.lines | 46, 59 |
| abstract_inverted_index.model | 2 |
| abstract_inverted_index.often | 20 |
| abstract_inverted_index.range | 15 |
| abstract_inverted_index.split | 129 |
| abstract_inverted_index.still | 86 |
| abstract_inverted_index.this, | 79 |
| abstract_inverted_index.where | 26, 116 |
| abstract_inverted_index.affect | 96 |
| abstract_inverted_index.common | 67 |
| abstract_inverted_index.exists | 143 |
| abstract_inverted_index.graphs | 1 |
| abstract_inverted_index.number | 76, 124 |
| abstract_inverted_index.obtain | 131 |
| abstract_inverted_index.planar | 133, 141 |
| abstract_inverted_index.recent | 105 |
| abstract_inverted_index.remove | 108 |
| abstract_inverted_index.result | 87 |
| abstract_inverted_index.(simple | 54 |
| abstract_inverted_index.between | 5, 56 |
| abstract_inverted_index.curves) | 55 |
| abstract_inverted_index.drawing | 142 |
| abstract_inverted_index.minimum | 123 |
| abstract_inverted_index.objects | 30 |
| abstract_inverted_index.whether | 139 |
| abstract_inverted_index.(points) | 38 |
| abstract_inverted_index.approach | 106 |
| abstract_inverted_index.consider | 103 |
| abstract_inverted_index.disjoint | 7 |
| abstract_inverted_index.drawing, | 25 |
| abstract_inverted_index.drawing. | 101, 134 |
| abstract_inverted_index.drawings | 71, 89 |
| abstract_inverted_index.however, | 80 |
| abstract_inverted_index.minimize | 74 |
| abstract_inverted_index.objects. | 10 |
| abstract_inverted_index.parallel | 44 |
| abstract_inverted_index.vertices | 37, 126, 149 |
| abstract_inverted_index.2-layered | 24 |
| abstract_inverted_index.Bipartite | 0 |
| abstract_inverted_index.crossings | 78, 93, 109 |
| abstract_inverted_index.expensive | 83 |
| abstract_inverted_index.parameter | 152 |
| abstract_inverted_index.splitting | 114, 145 |
| abstract_inverted_index.tractable | 153 |
| abstract_inverted_index.vertices, | 115 |
| abstract_inverted_index.vertices. | 63 |
| abstract_inverted_index.connecting | 60 |
| abstract_inverted_index.horizontal | 45 |
| abstract_inverted_index.objectives | 68 |
| abstract_inverted_index.visualized | 21, 32 |
| abstract_inverted_index.determining | 138 |
| abstract_inverted_index.readability | 98 |
| abstract_inverted_index.represented | 51 |
| abstract_inverted_index.applications | 17 |
| abstract_inverted_index.relationship | 4 |
| abstract_inverted_index.corresponding | 62 |
| abstract_inverted_index.relationships | 49 |
| abstract_inverted_index.visualizations | 112 |
| abstract_inverted_index.computationally | 82 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/8 |
| sustainable_development_goals[0].score | 0.4099999964237213 |
| sustainable_development_goals[0].display_name | Decent work and economic growth |
| citation_normalized_percentile |