wiki_research

commit 4b86ec12fce3c1a209ae58b330fca6f08c68906b
parent b8d10963826bb02cc0a250c7ac5f5d381b25bc0b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 14 Apr 2026 18:22:13 +0200

commit with codex

Diffstat:
crossing_number_computation
 | 
7
+++++++
simple_graph
 | 
2
++

2 files changed, 9 insertions(+), 0 deletions(-)
diff --git a/crossing_number_computation b/crossing_number_computation
@@ -0,0 +1,7 @@
+# Crossing number computation
+
+The [computational_problem] of computing the [crossing_number]
+
+It is [NP_hard], even on [simple_graphs] of bounded [pathwidth], cf [hlineny2026crossing]
+
+Up: [computational_problem], [crossing_number]
diff --git a/simple_graph b/simple_graph
@@ -7,3 +7,5 @@ A [graph] which is not a [multigraph], i.e., there cannot be multiple copies of 
 Up: [graph]
 
 See also: [set_semantics]
+
+Aliases: simple graphs