A New Algorithm for Graph Crossings, Hiding in Plain Sight

Oct 19, 2020 | Location Kirkwood

A New Algorithm for Graph Crossings, Hiding in Plain Sight

Two computer scientists found — in the unlikeliest of places — just the idea they needed to make a big leap in graph theory.

Stephanie DeMarco

 

This past October, as Jacob Holm and Eva Rotenberg were thumbing through a paper they’d posted a few months earlier, they realized they had been sitting on something big.

For decades computer scientists had been trying to develop a fast algorithm for determining when it’s possible to add edges to a graph so that it remains “planar,” meaning none of its edges cross each other. But the field had been unable to improve on an algorithm published over 20 years ago.

Holm and Rotenberg were surprised to find that their paper contained the insight needed to do a lot better. It “solved one of the major stumbling blocks we had with actually getting a real algorithm,” said Holm, a computer scientist at the University of Copenhagen. “We might have given the whole thing away.”

The two rushed to draft a new paper. They presented it in June at the ACM Symposium on Theory of Computing, where they detailed an exponentially better method for checking whether a graph is planar.

“The new algorithm is a remarkable tour de force,” said Giuseppe Italiano, a computer scientist at Luiss University and a co-author of the 1996 paper describing what is now the second-fastest algorithm. “When I co-authored that paper, I didn’t think that this could happen.”

Graphs are collections of nodes connected by edges. They can be used to represent everything from a social network to road systems to the electrical connections on a circuit board. In circuit boards, if the graph isn’t planar, it means that two wires cross each other and short-circuit.

As early as 1913, planar graphs came up in a brainteaser called the three-utilities problem, published in The Strand Magazine. It asked readers to connect three houses to three utilities — water, gas and electricity — without crossing any of the connections. It doesn’t take long to see that it can’t be done.

But it’s not always immediately obvious whether more complicated graphs are planar. And it’s even harder to tell whether a complicated planar graph stays planar when you start adding edges as you might when planning a new stretch of highway.

Computer scientists have been searching for an algorithm that can quickly determine whether you can make the desired change while keeping the graph planar and without checking every single part of the graph when only one small part is affected. The 1996 algorithm required a number of computational steps that was roughly proportional to the square root of the number of nodes in the graph.

“[It’s] much better than just doing it from scratch each time, but it’s not really good,” said Holm.

The new algorithm checks planarity in a number of steps proportional to the cube of the logarithm of the number of nodes in the graph — an exponential improvement. Holm and Rotenberg, a computer scientist at the Technical University of Denmark, achieved the speedup by taking advantage of a special property of planar graphs that they discovered last year.

To understand their method, the first thing to notice is that the same planar graph can be drawn multiple ways. In these different drawings, the connections remain the same, but the edges might be in different positions relative to one another.

For example, you can change drawing A into drawing B by flipping the triangle made by nodes 1, 2 and 3 over the edge connecting nodes 2 and 3. The top section of drawing B can also be reflected over nodes 4 and 5 to produce drawing C. The drawings look different, but they’re the same graph.

A graph with seven nodes being transformed by a series of flips.

Now imagine that you want to insert a new edge connecting two nodes in a planar graph, say nodes 1 and 6 in the example below. To do so, you’re going to perform a series of flips. From the starting position on the left it takes two flips to move node 1 into a space where it can be connected to node 6 without crossing any other edges.

 

A graphic showing how it's possible to manipulate a graph to connect two nodes without intersecting any other edges.

 

 

In their 2019 paper Holm and Rotenberg found that some drawings provide a more advantageous starting position for inserting an edge than others. These “good” drawings are only a few flips away from accepting the edge without breaking planarity.

What they belatedly recognized in October was that a flip that brings you closer to being able to add a new edge also brings the graph closer to resembling one of the good drawings they’d already identified. By showing that a series of flips inevitably moves a graph toward a favorable drawing, the new algorithm puts a backstop on the number of flips you could possibly need to perform before finding a way to insert an edge (provided the insertion is possible at all).

“We very quickly realized that with this new analysis, a conceptually very, very simple algorithm will solve the problem,” said Holm.

The new algorithm performs flips one at a time, searching for a solution. Eventually, one of two things happens: Either the algorithm finds a way to insert the desired edge, or the next flip undoes the previous flip — at which point the algorithm concludes there’s no way to add the edge.

“We call this the lazy-greedy [algorithm],” Rotenberg explained. “It only does the changes necessary to accommodate the edge.”

Their new method approaches — but doesn’t quite achieve — the performance of the best possible algorithm (or lower bound) for this kind of problem. The new algorithm also has to work through too many steps for most real-world applications, where the relevant graphs are usually simple enough to check with brute-force methods.

But for Holm and Rotenberg, the speed of the algorithm is less important than the insights that accelerated it. “Out of that understanding comes something fast,” said Rotenberg.

And Italiano thinks it may eventually help with real-world applications. “[It’s] likely to have, sooner or later, an impact also outside computer science and mathematics,” he said.

As for when an even faster algorithm will come along, no one knows. It could require a whole new breakthrough, or the secret ingredient may already be out there, waiting in a stack of old research papers.

Locations near
ME
Ashburn 0.93 mi
43330 Junction Plaza
#160
Ashburn, VA 20147
Sterling 4.07 mi
44 Pidgeon Hill Drive
#100
Sterling, VA 20165
Leesburg 5.69 mi
521 E Market St
#B
Leesburg, VA 20176
Herndon 7.66 mi
2465 Centreville Road
#J2
Herndon, VA 20171
Stone Ridge 7.88 mi
42020 Village Center Plaza
#100
Stone Ridge, VA 20105
Reston 8.62 mi
1424 North Point Village Center
Reston, VA 20194
Purcellville 12.72 mi
1020 E Main St
Ste L
Purcellville, VA 20132
North Potomac 13.58 mi
12150 Darnestown Rd
Gaithersburg, MD 20878
Centreville 14.52 mi
5959 Centreville Crest Ln
Centreville, VA 20121
Fairfax 14.67 mi
11891 Grand Commons Ave
Fairfax, VA 22030
Potomac 14.98 mi
10232 River Road
#B
Potomac, MD 20854
Germantown MD 15.03 mi
12800 Middlebrook Road
Germantown, MD 20874
Tysons 15.45 mi
328 Maple Ave E
#A
Vienna, VA 22180
Haymarket 17.87 mi
15125 Washington St
Haymarket, VA 20169
Rockville 18.19 mi
20 Courthouse Square
#106
Rockville, MD 20850
Mclean 18.23 mi
1320 Old Chain Bridge Road
Suite #190
McLean, VA 22101
Gaithersburg 18.71 mi
9132 Rothbury Drive
Gaithersburg, MD 20886
North Bethesda 20.42 mi
5268 Nicholson Ln
#N
Kensington, MD 20895
Falls Church 20.59 mi
6674 Arlington Blvd
Falls Church, VA 22042
Manassas 20.65 mi
9722 Liberia Ave
Manassas, VA 20110
Bristow 20.71 mi
12705 Braemar Village Pz
Bristow, VA 20136
Burke 20.82 mi
9411 Old Burke Lake Rd
#C
Burke, VA 22015
Bethesda 21.3 mi
4918 Fairmont Ave
Bethesda, MD 20814
Annandale 21.64 mi
7000 Columbia Pike
Annandale, VA 22003
Damascus 22.77 mi
9815 Main St
Damascus, MD 20872
Arlington, VA 23.29 mi
4801 1st St N
Arlington, VA 22203
Cathedral Heights 23.51 mi
3706 Macomb St NW
Washington, D.C., DC 20016
Olney 23.96 mi
18157 Village Center Dr
Olney, MD 20832
Downtown Silver Spring 24.94 mi
1133 East West Highway
Silver Spring, MD 20910
Lorton 25.06 mi
9027 Silverbrook Rd
#A
Fairfax Station, VA 22039
West Washington 25.69 mi

Washington, DC 20009
Alexandria City 25.7 mi
4605 Duke Street
Alexandria, VA 22304
Lake Ridge 26.5 mi
12473 Dillingham Square
Lake Ridge, VA 22192
Frederick North 26.7 mi
905 W. 7th Street
Frederick, MD 21701
Northern Silver Spring 26.75 mi
732 Cloverly Street
Silver Spring, MD 20905
Alexandria 27.17 mi
6483 Old Beulah Street
Alexandria, VA 22315
Warrenton 27.42 mi
512 Fletcher Drive
Warrenton, VA 20186
Mount Airy 28.24 mi
411 E Ridgeville Blvd
Mt Airy, MD 21771
Capitol Hill DC 28.48 mi
621 Pennsylvania Ave SE
1st-floor unit
Washington, DC 20003
Dale City 28.99 mi
5512 Staples Mill Plaza
Dale City, VA 22193
Mount Vernon 29.66 mi
7696 H Richmond Hwy
Alexandria, VA 22306
Beltsville 30.89 mi
10914 Baltimore Ave
#B
Beltsville, MD 20705
Clarksville 31.56 mi
12250 Clarksville Pike
#D
Clarksville, MD 21029
Laurel 35.02 mi
10095 Washington Blvd N
#136
Laurel, MD 20723
Woodmore 35.27 mi
9101 Woodmore Centre Drive
Lanham, MD 20706
Glenn Dale 35.83 mi
10559 Greenbelt Rd
Lanham, MD 20706
Sykesville 36.57 mi
1207 Liberty Rd.
#D-104
Sykesville, MD 21784
Ellicott City 37.11 mi
3290 Pine Orchard Lane
#B
Ellicott City, MD 21042
Winchester 37.62 mi
2512 S Pleasant Valley Rd
Winchester, VA 22601
Columbia 38.19 mi
8827 Centre Park Drive
#F
Columbia, MD 21045
Stafford 39.58 mi
263 Garrisonville Road
#104
Stafford, VA 22554
Bowie 41.26 mi
15231 Hall Rd
Bowie, MD 20721
Waldorf 42.24 mi
3022 Festival Way
Waldorf, MD 20601
Crofton 42.6 mi
1153 Route 3 North
#120
Crofton, MD 21054
Owings Mills 44.15 mi
9433 Common Brook Rd #100
Owings Mills, MD 21117
Pikesville 46.84 mi
1433 Reisterstown Rd
Pikesville, MD 21208
Dunkirk 49.92 mi
10735 Town Center Blvd
#7
Dunkirk, MD 20754