Barycentric coordinates of weighted edges

Given $K_n$ with weighted edges, we can fix an edge $e_{AB}$, iterate over all non-adjacent edges $e_{CD}in Esetminus e_{AD}$ and record how often $e_{AB}$ was in the lightest, intermediate or heaviest perfect matching of the subgraph induced by the the set $lbrace A,B,C,Drbrace$ of the pair’s adjacent vertices.

That procedure yields a vector of three values $(r,g,b), r+g+b = binom{n-2}{2}$ for every edge and can thus be interpreted as planar barycentric coordinates of the edges.

It is clear that these coordinates do not depend on changes to vertex weights and may thus provide a characterization of instances of combinatorial optimzation problems that also exhibit that independence from vertex weights; the Traveling Salesman Problem is prototypical in that respect.


have these barycentric coordinates of weighted edges already been mentioned or investigated w.r.t. usability for e.g. data analysis?

MathOverflow Asked by Manfred Weis on January 17, 2021

0 Answers

Add your own answers!

Related Questions

Twisted winding number

1  Asked on February 9, 2021 by jack-l


Writing papers in pre-LaTeX era?

28  Asked on February 3, 2021 by psihodelia


Ask a Question

Get help from others!

© 2022 All rights reserved.