Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A new algorithm for graph crossings, hiding in plain sight (2020)

quantamagazine.org

Post reply on HN
Print view View original

41–44 of 44 posts

Re: A new algorithm for graph crossings, hiding in plain sight (2020)

#41

Post by thomasahle »

not2b wrote: post #19
thomasahle wrote: post #13

Earlier quoted context omitted.

I work with the researchers, and I think they'll be interested in knowing which version of the problem practitioners like yourself are most interested in. Do you ever add/remove edges, perhaps in bulk? Or do are you mostly interested in finding "best possible" layouts for static datasets?

I don't work on placement problems, though part of my work provides input for the placement problem (produce an optimized logic netlist that then has to be placed and routed). But if I can suggest something in the same ballpark: imagine that you have a large graph and you want to partition it into a small number of partitions (say, 4 to 10) of similar size. You want each partition to be a planar graph, and you want t…

That sounds like a nice problem: Partition the vertices into planar sub-graphs, minimizing the number of edges between parts.

It's not really a dynamic problem anymore. It also becomes very specific to ASIC. Do you know if it has already been studied?

Re: A new algorithm for graph crossings, hiding in plain sight (2020)

#42

Post by orange3xchicken »

thomasahle wrote: post #41
not2b wrote: post #19

Earlier quoted context omitted.

I don't work on placement problems, though part of my work provides input for the placement problem (produce an optimized logic netlist that then has to be placed and routed). But if I can suggest something in the same ballpark: imagine that you have a large graph and you want to partition it into a small number of partitions (say, 4 to 10) of similar size. You want each partition to be a planar graph, and you want t…

That sounds like a nice problem: Partition the vertices into planar sub-graphs, minimizing the number of edges between parts. It's not really a dynamic problem anymore. It also becomes very specific to ASIC. Do you know if it has already been studied?

Someone correct me, but I think hMetis is one popular software/algorithm for multi-level graph/hypergraph partitioning. There is also KaHyPar which is a bit more academic.

Re: A new algorithm for graph crossings, hiding in plain sight (2020)

#43

Post by TechBro8615 »

phaemon wrote: post #4

I like graph theory. You draw some shapes, you draw some lines. It's like the kind of things you can do with your crayons. I reckon kids could be introduced to it earlier in friendlier language.

As someone who hated math and was really bad at it since calculus (mostly due to lack of rigor), yes. Once I got to algorithms class, I struggled at first but after a session with my (really excellent) professor, something “clicked”.

I really think graph theory and discrete math in general should be taught much earlier. Maybe even before (or alongside) calculus in high school. Calculus isn’t really a legitimate prerequisite in this case.

Post reply on HN